Posts published in December 2018

花花酱 LeetCode 963. Minimum Area Rectangle II

By zxi on December 26, 2018

Given a set of points in the xy-plane, determine the minimum area of any rectangle formed from these points, with sides not necessarily parallel to the x and y axes.

If there isn’t any rectangle, return 0.

Example 1:

Input: [[1,2],[2,1],[1,0],[0,1]]
Output: 2.00000
Explanation: The minimum area rectangle occurs at [1,2],[2,1],[1,0],[0,1], with an area of 2.

Example 2:

Input: [[0,1],[2,1],[1,1],[1,0],[2,0]]
Output: 1.00000
Explanation: The minimum area rectangle occurs at [1,0],[1,1],[2,1],[2,0], with an area of 1.

Example 3:

Input: [[0,3],[1,2],[3,1],[1,3],[2,1]]
Output: 0
Explanation: There is no possible rectangle to form from these points.

Example 4:

Input: [[3,1],[1,1],[0,1],[2,1],[3,3],[3,2],[0,2],[2,3]]
Output: 2.00000
Explanation: The minimum area rectangle occurs at [2,1],[2,3],[3,3],[3,1], with an area of 2.

Note:

1 <= points.length <= 50
0 <= points[i][0] <= 40000
0 <= points[i][1] <= 40000
All points are distinct.
Answers within 10^-5 of the actual value will be accepted as correct.

Solution: HashTable

Iterate all possible triangles and check the opposite points that creating a quadrilateral.

Time complexity: O(n^3)
Space complexity: O(n)

C++

class Solution {

public:

double minAreaFreeRect(vector<vector<int>>& points) {

constexpr double INF_AREA = 1e100;

const auto n = points.size();

unordered_set<int> s;

for (const auto& p : points)

s.insert(p[0] << 16 | p[1]);

double min_area = INF_AREA;

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

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

if (i == j) continue;

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

if (i == k || j == k) continue;

const auto& p1 = points[i];

const auto& p2 = points[j];

const auto& p3 = points[k];

int dot = (p2[0] - p1[0]) * (p3[0] - p1[0]) +

(p2[1] - p1[1]) * (p3[1] - p1[1]);

if (dot != 0) continue;

int p4_x = p2[0] + p3[0] - p1[0];

int p4_y = p2[1] + p3[1] - p1[1];

if (!s.count(p4_x << 16 | p4_y)) continue;

double a = pow(p2[0] - p1[0], 2) + pow(p2[1] - p1[1], 2);

double b = pow(p3[0] - p1[0], 2) + pow(p3[1] - p1[1], 2);

double area = a * b;

min_area = min(min_area, area);

}

return min_area < INF_AREA ? sqrt(min_area) : 0;

}

};

花花酱 LeetCode 962. Maximum Width Ramp

By zxi on December 25, 2018

Given an array A of integers, a ramp is a tuple (i, j) for which i < j and A[i] <= A[j]. The width of such a ramp is j - i.

Find the maximum width of a ramp in A. If one doesn’t exist, return 0.

Example 1:

Input: [6,0,8,2,1,5] 
Output: 4 
Explanation:  The maximum width ramp is achieved at (i, j) = (1, 5): A[1] = 0 and A[5] = 5.

Example 2:

Input: [9,8,1,0,1,9,4,0,4,1] 
Output: 7 
Explanation:  The maximum width ramp is achieved at (i, j) = (2, 9): A[2] = 1 and A[9] = 1.

Note:

2 <= A.length <= 50000
0 <= A[i] <= 50000

Solution: Stack

Using a stack to store start candidates’ (decreasing order) index
Scan from right to left, compare the current number with the one on the top of the stack, pop if greater.

e.g.
A = [6,0,8,2,1,5]
stack = [0, 1] => [6, 0]
cur: A[5] = 5, stack.top = A[1] = 0, ramp = 5, stack.pop()
cur: A[4] = 1, stack.top = A[0] = 6
cur: A[3] = 2, stack.top = A[0] = 6
cur: A[2] = 8, stack.top = A[0] = 6, ramp = 2, stack.pop()
stack.isEmpty() => END

C++

// Author: Huahua, running time: 44 ms

class Solution {

public:

int maxWidthRamp(vector<int>& A) {

stack<int> s;

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

if (s.empty() || A[i] < A[s.top()])

s.push(i);

int ans = 0;

for (int i = A.size() - 1; i >= 0; --i)

while (!s.empty() && A[i] >= A[s.top()]) {

ans = max(ans, i - s.top());

s.pop();

}

return ans;

}

};

Python3

# Author: Huahua, running time: 92 ms

class Solution:

def maxWidthRamp(self, A):

s = []

for i in range(len(A)):

if not s or A[i] < A[s[-1]]: s.append(i)

ans = 0

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

while s and A[i] >= A[s[-1]]:

ans = max(ans, i - s.pop())

return ans

花花酱 LeetCode 961. N-Repeated Element in Size 2N Array

By zxi on December 23, 2018

In a array A of size 2N, there are N+1 unique elements, and exactly one of these elements is repeated N times.

Return the element repeated N times.

Example 1:

Input: [1,2,3,3]
Output: 3

Example 2:

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

Example 3:

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

Note:

4 <= A.length <= 10000
0 <= A[i] < 10000
A.length is even

Solution: Randomization

Randomly pick two numbers in the array, if they are the same (25% probability) return the number, do it until the two numbers are the same.

Time complexity: O(1) expected 4
Space complexity: O(1)

C++

// Author: Huahua, running time: 72 ms

class Solution {

public:

int repeatedNTimes(vector<int>& A) {

int i = 0;

int j = 0;

while (i == j || A[i] != A[j]) {

i = rand() % A.size();

j = rand() % A.size();

}

return A[i];

}

};

花花酱 LeetCode 78. Subsets

By zxi on December 22, 2018

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

Input: nums = [1,2,3]
Output:[  [3],  [1],  [2],  [1,2,3],  [1,3],  [2,3],  [1,2],  []]

Solution: Combination

Time complexity: O(2^n)
Space complexity: O(n)

Implemention 1: DFS

C++

// Author: Huahua, running time: 4 ms

class Solution {

public:

vector<vector<int>> subsets(vector<int>& nums) {

vector<vector<int>> ans;

vector<int> cur;

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

dfs(nums, i, 0, cur, ans);

return ans;

}

private:

void dfs(const vector<int>& nums, int n, int s,

vector<int>& cur, vector<vector<int>>& ans) {

if (n == cur.size()) {

ans.push_back(cur);

return;

}

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

cur.push_back(nums[i]);

dfs(nums, n, i + 1, cur, ans);

cur.pop_back();

}

};

Python3

# Author: Huahua, running time: 60 ms

class Solution:

def subsets(self, nums):

ans = []

def dfs(n, s, cur):

if n == len(cur):

ans.append(cur.copy())

return

for i in range(s, len(nums)):

cur.append(nums[i])

dfs(n, i + 1, cur)

cur.pop()

for i in range(len(nums) + 1):

dfs(i, 0, [])

return ans

Implementation 2: Binary

C++

// Author: Huahua, running time: 4 ms

class Solution {

public:

vector<vector<int>> subsets(vector<int>& nums) {

const int n = nums.size();

vector<vector<int>> ans;

for (int s = 0; s < 1 << n; ++s) {

vector<int> cur;

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

if (s & (1 << i)) cur.push_back(nums[i]);

ans.push_back(cur);

}

return ans;

}

};

Python3

# Author: Huahua, 40 ms

class Solution:

def subsets(self, nums):

n = len(nums)

return [[nums[i] for i in range(n) if s & 1 << i > 0] for s in range(1 << n)]

花花酱 LeetCode 220. Contains Duplicate III

By zxi on December 20, 2018

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.

Example 1:

Input: nums = [1,2,3,1], k = 3, t = 0
Output: true

Example 2:

Input: nums = [1,0,1,1], k = 1, t = 2
Output: true

Example 3:

Input: nums = [1,5,9,1,5,9], k = 2, t = 3
Output: false

Solution: Sliding Window + Multiset (OrderedSet)

Maintaining a sliding window of sorted numbers of k + 1. After the i-th number was inserted into the sliding window, check whether its left and right neighbors satisfy abs(nums[i] – neighbor) <= t

Time complexity: O(nlogk)
Space complexity: O(k)

C++

// Author: Huahua, running time: 12 ms

class Solution {

public:

bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {

multiset<long> s;

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

if (i > k)

s.erase(s.find(nums[i - k - 1]));

auto it = s.insert(nums[i]);

if (it != begin(s) && *it - *prev(it) <= t)

return true;

if (next(it) != end(s) && *next(it) - *it <= t)

return true;

}

return false;

}

};