Posts published in “Algorithms”

花花酱 LeetCode 18. 4Sum

By zxi on September 19, 2018

Problem

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

The solution set must not contain duplicate quadruplets.

Example:

Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

Solution 1: Sorting + Binary Search

Time complexity: O(n^3 log n + klogk)

Space complexity: O(k)

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> fourSum(vector<int> &num, int target) {

set<vector<int>> h;

sort(num.begin(), num.end());

int n = num.size();

for (int i = 0; i < n; i++) {

for (int j = i + 1; j < n; j++) {

for(int k = j + 1; k < n; k++) {

int t = target - num[i] - num[j] - num[k];

if (t < num[k]) break;

if (!std::binary_search(num.begin() + k + 1, num.end(), t)) continue;

h.insert({num[i], num[j], num[k], t});

}

return vector<vector<int>>(begin(h), end(h));

}

};

C++ opt

// Author: Huahua

class Solution {

public:

vector<vector<int>> fourSum(vector<int> &num, int target) {

sort(num.begin(), num.end());

if (target > 0 && target > 4 * num.back()) return {};

if (target < 0 && target < 4 * num.front()) return {};

set<vector<int>> h;

int n = num.size();

for (int i = 0; i < n; i++) {

for (int j = i + 1; j < n; j++) {

for(int k = j + 1; k < n; k++) {

int t = target - num[i] - num[j] - num[k];

if (t < num[k]) break;

if (!std::binary_search(num.begin() + k + 1, num.end(), t)) continue;

h.insert({num[i], num[j], num[k], t});

}

return vector<vector<int>>(begin(h), end(h));

}

};

Solution 2: Sorting + HashTable

Time complexity: O(n^3 + klogk)

Space complexity: O(n + k)

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> fourSum(vector<int> &num, int target) {

sort(num.begin(), num.end());

if (target > 0 && target > 4 * num.back()) return {};

if (target < 0 && target < 4 * num.front()) return {};

unordered_map<int, int> index;

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

index[num[i]] = i;

set<vector<int>> h;

int n = num.size();

for (int i = 0; i < n; i++) {

for (int j = i + 1; j < n; j++) {

for(int k = j + 1; k < n; k++) {

int t = target - num[i] - num[j] - num[k];

if (t < num[k]) break;

auto it = index.find(t);

if (it == index.end() || it->second <= k) continue;

h.insert({num[i], num[j], num[k], t});

}

return vector<vector<int>>(begin(h), end(h));

}

};

Problem

Given an array A of non-negative integers, return an array consisting of all the even elements of A, followed by all the odd elements of A.

You may return any answer array that satisfies this condition.

Example 1:

Input: [3,1,2,4]

Output: [2,4,3,1]

The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.

Note:

1 <= A.length <= 5000
0 <= A[i] <= 5000

Solution 1: Split Odd/Even

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua, 44 ms

class Solution {

public:

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

vector<int> even;

vector<int> odd;

for (int a : A) {

if (a % 2) odd.push_back(a);

else even.push_back(a);

}

even.insert(end(even), begin(odd), end(odd));

return even;

}

};

Solution 2: Stable sort by key % 2

Time complexity: O(nlogn)

Space complexity: O(1) in-place

C++

// Author: Huahua, 52 ms

class Solution {

public:

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

stable_sort(begin(A), end(A), [](int a, int b){

return a % 2 < b % 2;

});

return A;

}

};

花花酱 LeetCode 668. Kth Smallest Number in Multiplication Table

By zxi on September 10, 2018

Problem

Nearly every one have used the Multiplication Table. But could you find out the k-th smallest number quickly from the multiplication table?

Given the height m and the length n of a m * n Multiplication Table, and a positive integer k, you need to return the k-th smallest number in this table.

Example 1:

Input: m = 3, n = 3, k = 5
Output: 
Explanation: 
The Multiplication Table:
1	2	3
2	4	6
3	6	9

The 5-th smallest number is 3 (1, 2, 2, 3, 3).

Example 2:

Input: m = 2, n = 3, k = 6
Output: 
Explanation: 
The Multiplication Table:
1	2	3
2	4	6

The 6-th smallest number is 6 (1, 2, 2, 3, 4, 6).

Note:

The m and n will be in the range [1, 30000].
The k will be in the range [1, m * n]

Solution 1: Nth element (MLE)

Time complexity: O(mn)

Space complexity: O(mn)

C++

// 59 / 69 test cases passed.

class Solution {

public:

int findKthNumber(int m, int n, int k) {

vector<int> s(m * n);

auto it = begin(s);

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

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

*it++ = i * j;

nth_element(begin(s), begin(s) + k - 1, end(s));

return s[k - 1];

}

};

Solution2 : Binary Search

Find first x such that there are k elements less or equal to x in the table.

Time complexity: O(m*log(m*n))

Space complexity: O(1)

C++

// Author: Huahua, 12 ms

class Solution {

public:

int findKthNumber(int m, int n, int k) {

int l = 1;

int r = m * n + 1;

while (l < r) {

int x = l + (r - l) / 2;

if (LEX(m, n, x) >= k)

r = x;

else

l = x + 1;

}

return l;

}

private:

// Returns # of elements in the m*n table that are <= x

int LEX(int m, int n, int x) {

int count = 0;

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

count += min(n, x / i);

return count;

}

};

Java

// Author: Huahua, 16 ms

class Solution {

public int findKthNumber(int m, int n, int k) {

int l = 1;

int r = m * n + 1;

while (l < r) {

int x = l + (r - l) / 2;

if (LEX(m, n, x) >= k)

r = x;

else

l = x + 1;

}

return l;

}

// Returns # of elements in the m*n table that are <= x

private int LEX(int m, int n, int x) {

int count = 0;

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

count += Math.min(n, x / i);

return count;

}

Python3

# Author: Huahua, 976 ms

class Solution:

def findKthNumber(self, m, n, k):

def LEX(m, n, x, k):

count = 0

for i in range(1, min(m + 1, x + 1)):

count += min(n, x // i)

if count >= k: return count

return count

l = 1

r = m * n + 1

while l < r:

x = l + (r - l) // 2

if LEX(m, n, x, k) >= k:

r = x

else:

l = x + 1

return l

Solution:

C++

// Author: Huahua

class Solution {

public:

bool isMonotonic(vector<int>& A) {

bool inc = true;

bool dec = true;

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

inc &= A[i] >= A[i - 1];

dec &= A[i] <= A[i - 1];

}

return inc || dec;

}

};

Java

class Solution {

public boolean isMonotonic(int[] A) {

boolean inc = true;

boolean dec = true;

for (int i = 1; i < A.length; ++i) {

inc &= A[i] >= A[i - 1];

dec &= A[i] <= A[i - 1];

}

return inc || dec;

}

Python

# Author: Huahua

class Solution:

def isMonotonic(self, A):

inc = True;

dec = True;

for i in range(1, len(A)):

inc = inc and A[i] >= A[i - 1]

dec = dec and A[i] <= A[i - 1]

return inc or dec;

花花酱 LeetCode 566. Reshape the Matrix

By zxi on August 16, 2018

Problem

In MATLAB, there is a very useful function called ‘reshape’, which can reshape a matrix into a new one with different size but keep its original data.

You’re given a matrix represented by a two-dimensional array, and two positive integers r and c representing the row number and column number of the wanted reshaped matrix, respectively.

The reshaped matrix need to be filled with all the elements of the original matrix in the same row-traversing order as they were.

If the ‘reshape’ operation with given parameters is possible and legal, output the new reshaped matrix; Otherwise, output the original matrix.

Example 1:

Input: 
nums = 
[[1,2],
 [3,4]]
r = 1, c = 4
Output: 
[[1,2,3,4]]
Explanation:
The row-traversing of nums is [1,2,3,4]. The new reshaped matrix is a 1 * 4 matrix, fill it row by row by using the previous list.

Example 2:

Input: 
nums = 
[[1,2],
 [3,4]]
r = 2, c = 4
Output: 
[[1,2],
 [3,4]]
Explanation:
There is no way to reshape a 2 * 2 matrix to a 2 * 4 matrix. So output the original matrix.

Note:

The height and width of the given matrix is in range [1, 100].
The given r and c are all positive.

Solution1: Brute Force

Time complexity: O(mn)

Space complexity: O(mn)

// Author: Huahua

// Running time: 32 ms

class Solution {

public:

vector<vector<int>> matrixReshape(vector<vector<int>>& nums, int r, int c) {

if (nums.size() == 0) return nums;

int m = nums.size();

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

if (m * n != r * c) return nums;

// new matrix r*c

vector<vector<int>> ans(r, vector<int>(c));

for(int i = 0; i < m * n;++i) {

int src_y = i / n;

int src_x = i % n;

int dst_y = i / c;

int dst_x = i % c;

ans[dst_y][dst_x] = nums[src_y][src_x];

}

return ans;

}

};

Posts published in “Algorithms”

花花酱 LeetCode 18. 4Sum

Problem

Solution 1: Sorting + Binary Search

C++

C++ opt

Solution 2: Sorting + HashTable

C++

Related Problems

花花酱 LeetCode 905. Sort Array By Parity

Problem

Solution 1: Split Odd/Even

C++

Solution 2: Stable sort by key % 2

C++

花花酱 LeetCode 668. Kth Smallest Number in Multiplication Table

Problem

Solution 1: Nth element (MLE)

C++

Solution2 : Binary Search

C++

Java

Python3

Related Problems

花花酱 LeetCode 896. Monotonic Array

Solution:

C++

Java

Python

花花酱 LeetCode 566. Reshape the Matrix

Problem

Solution1: Brute Force