花花酱 LeetCode 303. Range Sum Query – Immutable

By zxi on August 17, 2018

Problem

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

Example:

Given nums = [-2, 0, 3, -5, 2, -1]

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

Note:

You may assume that the array does not change.
There are many calls to sumRange function.

Solution: Prefix sum

sums[i] = nums[0] + nums[1] + … + nums[i]

sumRange(i, j) = sums[j] – sums[i – 1]

Time complexity: pre-compute: O(n), query: O(1)

Space complexity: O(n)

// Author: Huahua

// Running time: 112 ms

class NumArray {

public:

NumArray(vector<int> nums): sums_(nums) {

if (nums.empty()) return;

for (int i = 1; i < nums.size();++i)

sums_[i] += sums_[i - 1];

}

int sumRange(int i, int j) {

if (i == 0) return sums_[j];

return sums_[j] - sums_[i-1];

}

private:

vector<int> sums_;

};

花花酱 LeetCode 561. Array Partition I

By zxi on August 16, 2018

Problem

Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a₁, b₁), (a₂, b₂), …, (a_n, b_n) which makes sum of min(a_i, b_i) for all i from 1 to n as large as possible.

Example 1:

Input: [1,4,3,2]

Output: 4
Explanation: n is 2, and the maximum sum of pairs is 4 = min(1, 2) + min(3, 4).

Note:

n is a positive integer, which is in the range of [1, 10000].
All the integers in the array will be in the range of [-10000, 10000].

Solution 1: Sorting

Time complexity: O(nlogn)

Space complexity: O(1)

// Author: Huahua

// Running time: 52 ms

class Solution {

public:

int arrayPairSum(vector<int>& nums) {

std::sort(nums.begin(), nums.end());

int ans = 0;

for(int i = 0; i < nums.size(); i += 2)

ans += nums[i];

return ans;

}

};

Solution 2: HashTable

Time complexity: O(n + max(nums) – min(nums))

Space complexity: O(max(nums) – min(nums))

// Author: Huahua

// Running time: 39 ms

class Solution {

public:

int arrayPairSum(vector<int>& nums) {

const int max_val = *max_element(begin(nums), end(nums));

const int min_val = *min_element(begin(nums), end(nums));

const int offset = -min_val;

vector<int> c(max_val - min_val + 1);

for (int num : nums)

++c[num + offset];

int ans = 0;

int index = 0;

int n = min_val;

while (n <= max_val) {

if (c[n + offset] == 0) {

++n;

continue;

}

ans += (++index & 1) ? n : 0;

--c[n + offset];

}

return ans;

}

};

花花酱 LeetCode 739. Daily Temperatures

By zxi on July 16, 2018

Problem

Given a list of daily temperatures, produce a list that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.

For example, given the list temperatures = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].

Solution: Stack

Use a stack to track indices of future warmer days. From top to bottom: recent to far away.

Time complexity: O(n)

Space complexity: O(n)

// Author: Huahua

// Running time: 148 ms

class Solution {

public:

vector<int> dailyTemperatures(vector<int>& temperatures) {

const int n = temperatures.size();

stack<int> s;

vector<int> ans(n);

for (int i = n - 1; i >= 0; --i) {

while (!s.empty() && temperatures[s.top()] <= temperatures[i]) s.pop();

ans[i] = s.empty() ? 0 : s.top() - i;

s.push(i);

}

return ans;

}

};

花花酱 LeetCode 350. Intersection of Two Arrays II

By zxi on July 14, 2018

Problem

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2].

Note:

Each element in the result should appear as many times as it shows in both arrays.
The result can be in any order.

Follow up:

What if the given array is already sorted? How would you optimize your algorithm?
What if nums1‘s size is small compared to nums2‘s size? Which algorithm is better?
What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

Solution1: Hashtable

Time complexity: O(m + n)

Space complexity: O(m)

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {

unordered_map<int, int> count;

vector<int> ans;

for (int num : nums1)

++count[num];

for (int num : nums2)

if (count.count(num) &&count[num] > 0) {

--count[num];

ans.push_back(num);

}

return ans;

}

};

花花酱 LeetCode 867. Transpose Matrix

By zxi on July 8, 2018

Given a matrix A, return the transpose of A.

The transpose of a matrix is the matrix flipped over it’s main diagonal, switching the row and column indices of the matrix.

Example 1:

Input: [[1,2,3],[4,5,6],[7,8,9]]
Output: [[1,4,7],[2,5,8],[3,6,9]]

Example 2:

Input: [[1,2,3],[4,5,6]]
Output: [[1,4],[2,5],[3,6]]

Note:

1 <= A.length <= 1000
1 <= A[0].length <= 1000

Solution: Brute Force

Time complexity: O(mn)

Space complexity: O(mn)

C++

// Author: Huahua

// Running time: 16 ms

class Solution {

public:

vector<vector<int>> transpose(vector<vector<int>>& A) {

int m = A.size();

int n = A[0].size();

vector<vector<int>> ans(n, vector<int>(m));

for (int i = 0; i < m; ++i)

for (int j = 0; j < n; ++j)

ans[j][i] = A[i][j];

return ans;

}

};

Posts tagged as “array”

花花酱 LeetCode 303. Range Sum Query – Immutable

Problem

Solution: Prefix sum

花花酱 LeetCode 561. Array Partition I

Problem

Solution 1: Sorting

Solution 2: HashTable

花花酱 LeetCode 739. Daily Temperatures

Problem

Solution: Stack

花花酱 LeetCode 350. Intersection of Two Arrays II

Problem

Solution1: Hashtable

花花酱 LeetCode 867. Transpose Matrix

Solution: Brute Force

C++