Posts tagged as “hard”

花花酱 LeetCode 1354. Construct Target Array With Multiple Sums

By zxi on February 16, 2020

Given an array of integers target. From a starting array, A consisting of all 1’s, you may perform the following procedure :

let x be the sum of all elements currently in your array.
choose index i, such that 0 <= i < target.size and set the value of A at index i to x.
You may repeat this procedure as many times as needed.

Return True if it is possible to construct the target array from A otherwise return False.

Example 1:

Input: target = [9,3,5]
Output: true
Explanation: Start with [1, 1, 1] 
[1, 1, 1], sum = 3 choose index 1
[1, 3, 1], sum = 5 choose index 2
[1, 3, 5], sum = 9 choose index 0
[9, 3, 5] Done

Example 2:

Input: target = [1,1,1,2]
Output: false
Explanation: Impossible to create target array from [1,1,1,1].

Example 3:

Input: target = [8,5]
Output: true

Constraints:

N == target.length
1 <= target.length <= 5 * 10^4
1 <= target[i] <= 10^9

Solution: Backwards Simulation

Start with the largest number in the array, since it should be the sum of all previous numbers.

[9,3,5] => [9 – (3+5), 3, 5] => [1, 3, 5] => [1, 3, 5 – (1+3)] => [1, 3, 1] => [1, 3 – (1+1), 1] => [1,1,1] done

Time complexity: O(n + log(n*t)*logn)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

bool isPossible(vector<int>& target) {

priority_queue<int> q(begin(target), end(target));

long sum = accumulate(begin(target), end(target), 0LL);

while (true) {

int t = q.top(); q.pop();

sum -= t;

if (t == 1 || sum == 1) return true;

if (t < sum || sum == 0 || t % sum == 0) return false;

t %= sum;

sum += t;

q.push(t);

}

return true;

}

};

花花酱 LeetCode 84. Largest Rectangle in Histogram

By zxi on February 14, 2020

Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

Example:

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

Solution 1: Monotonic Stack

Use a monotonic stack to maintain the higher bars’s indices in ascending order.
When encounter a lower bar, pop the tallest bar and use it as the bottleneck to compute the area.

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

C++

// Author: Huahua, 12ms, 10.7MB

class Solution {

public:

int largestRectangleArea(vector<int>& heights) {

heights.push_back(0);

const int n = heights.size();

stack<int> s;

int ans = 0;

int i = 0;

while (i < n) {

if (s.empty() || heights[i] >= heights[s.top()]) {

s.push(i++);

} else {

int h = heights[s.top()]; s.pop();

int w = s.empty() ? i : i - s.top() - 1;

ans = max(ans, h * w);

}

return ans;

}

};

花花酱 LeetCode 1349. Maximum Students Taking Exam

By zxi on February 9, 2020

Given a m * n matrix seats that represent seats distributions in a classroom. If a seat is broken, it is denoted by '#' character otherwise it is denoted by a '.' character.

Students can see the answers of those sitting next to the left, right, upper left and upper right, but he cannot see the answers of the student sitting directly in front or behind him. Return the maximum number of students that can take the exam together without any cheating being possible..

Students must be placed in seats in good condition.

Example 1:

Input: seats = [["#",".","#","#",".","#"],
                [".","#","#","#","#","."],
                ["#",".","#","#",".","#"]]
Output: 4
Explanation: Teacher can place 4 students in available seats so they don't cheat on the exam.

Example 2:

Input: seats = [[".","#"],
                ["#","#"],
                ["#","."],
                ["#","#"],
                [".","#"]]
Output: 3
Explanation: Place all students in available seats.

Example 3:

Input: seats = [["#",".",".",".","#"],
                [".","#",".","#","."],
                [".",".","#",".","."],
                [".","#",".","#","."],
                ["#",".",".",".","#"]]
Output: 10
Explanation: Place students in available seats in column 1, 3 and 5.

Constraints:

seats contains only characters '.' and'#'.
m == seats.length
n == seats[i].length
1 <= m <= 8
1 <= n <= 8

Solution 1: DFS (TLE)

Time complexity: O(2^(m*n)) = O(2^64)
Space complexity: O(m*n)

Solution 2: DP

Since how to fill row[i+1] only depends on row[i]’s state, we can define

dp[i][s] as the max # of students after filling i rows and s (as a binary string) is the states i-th row.

dp[i+1][t] = max{dp[i][s] + bits(t)} if row[i] = s && row[i +1] = t is a valid state.

Time complexity: O(m*2^(n+n)*n) = O(2^22)
Space complexity: O(m*2^n) = O(2^11) -> O(2^n)

C++

// Author: Huahua

class Solution {

public:

int maxStudents(vector<vector<char>>& seats) {

int m = seats.size();

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

vector<vector<int>> dp(m + 1, vector<int>(1 << n));

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

for (int l = 0; l < (1 << n); ++l)

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

bool flag = true;

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

if (!(c & (1 << j))) continue;

if (seats[i][j] == '#') flag = false;

bool l = j == 0 ? false : (c & (1 << (j - 1)));

bool r = j == n - 1 ? false : (c & (1 << (j + 1)));

bool ul = (j == 0 || i == 0) ? false : (l & (1 << (j - 1)));

bool ur = (j == n - 1 || i == 0) ? false : (l & (1 << (j + 1)));

if (l || r || ul || ur) flag = false;

}

if (flag)

dp[i + 1][c] = max(dp[i + 1][c], dp[i][l] + __builtin_popcount(c));

}

return *max_element(begin(dp[m]), end(dp[m]));

}

};

C++

// Author: Huahua

class Solution {

public:

int maxStudents(vector<vector<char>>& seats) {

const int m = seats.size();

const int n = seats[0].size();

vector<int> s(m + 1);

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

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

s[i] |= (seats[i - 1][j] == '.') << j;

vector<vector<int>> dp(m + 1, vector<int>(1 << n));

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

for (int c = s[i];;c = (c - 1) & s[i]) {

if (c & (c >> 1)) continue;

for (int l = s[i - 1];;l = (l - 1) & s[i - 1]) {

if (!(l & (c >> 1)) && !((l >> 1) & c))

dp[i][c] = max(dp[i][c], dp[i - 1][l] + __builtin_popcount(c));

if (l == 0) break;

}

if (c == 0) break;

}

return *max_element(begin(dp[m]), end(dp[m]));

}

};

花花酱 LeetCode 1345. Jump Game IV

By zxi on February 8, 2020

Given an array of integers arr, you are initially positioned at the first index of the array.

In one step you can jump from index i to index:

i + 1 where: i + 1 < arr.length.
i - 1 where: i - 1 >= 0.
j where: arr[i] == arr[j] and i != j.

Return the minimum number of steps to reach the last index of the array.

Notice that you can not jump outside of the array at any time.

Example 1:

Input: arr = [100,-23,-23,404,100,23,23,23,3,404]
Output: 3
Explanation: You need three jumps from index 0 --> 4 --> 3 --> 9. Note that index 9 is the last index of the array.

Example 2:

Input: arr = [7]
Output: 0
Explanation: Start index is the last index. You don't need to jump.

Example 3:

Input: arr = [7,6,9,6,9,6,9,7]
Output: 1
Explanation: You can jump directly from index 0 to index 7 which is last index of the array.

Example 4:

Input: arr = [6,1,9]
Output: 2

Example 5:

Input: arr = [11,22,7,7,7,7,7,7,7,22,13]
Output: 3

Constraints:

1 <= arr.length <= 5 * 10^4
-10^8 <= arr[i] <= 10^8

Solution: HashTable + BFS

Use a hashtable to store the indices of each unique number.

each index i has neighbors (i-1, i + 1, hashtable[arr[i]])

Use BFS to find the shortest path in this unweighted graph.

Key optimization, clear hashtable[arr[i]] after the first use, since all nodes are already on queue, no longer needed.

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

C++

// Author: Huahua, 124 ms, 30.5 MB

class Solution {

public:

int minJumps(vector<int>& arr) {

const int n = arr.size();

unordered_map<int, vector<int>> m;

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

m[arr[i]].push_back(i);

vector<int> seen(n);

queue<int> q({0});

seen[0] = 1;

int steps = 0;

while (!q.empty()) {

int size = q.size();

while (size--) {

int i = q.front(); q.pop();

if (i == n - 1) return steps;

if (i - 1 >= 0 && !seen[i - 1]++) q.push(i - 1);

if (i + 1 < n && !seen[i + 1]++) q.push(i + 1);

auto it = m.find(arr[i]);

if (it == m.end()) continue;

for (int nxt : it->second)

if (!seen[nxt]++) q.push(nxt);

m.erase(it); // no longer needed.

}

++steps;

}

return -1;

}

};

花花酱 LeetCode 1344. Jump Game V

By zxi on February 1, 2020

Given an array of integers arr and an integer d. In one step you can jump from index i to index:

i + x where: i + x < arr.length and 0 < x <= d.
i - x where: i - x >= 0 and 0 < x <= d.

In addition, you can only jump from index i to index j if arr[i] > arr[j] and arr[i] > arr[k] for all indices k between i and j (More formally min(i, j) < k < max(i, j)).

You can choose any index of the array and start jumping. Return the maximum number of indices you can visit.

Notice that you can not jump outside of the array at any time.

Example 1:

Input: arr = [6,4,14,6,8,13,9,7,10,6,12], d = 2
Output: 4
Explanation: You can start at index 10. You can jump 10 --> 8 --> 6 --> 7 as shown.
Note that if you start at index 6 you can only jump to index 7. You cannot jump to index 5 because 13 > 9. You cannot jump to index 4 because index 5 is between index 4 and 6 and 13 > 9.
Similarly You cannot jump from index 3 to index 2 or index 1.

Example 2:

Input: arr = [3,3,3,3,3], d = 3
Output: 1
Explanation: You can start at any index. You always cannot jump to any index.

Example 3:

Input: arr = [7,6,5,4,3,2,1], d = 1
Output: 7
Explanation: Start at index 0. You can visit all the indicies.

Example 4:

Input: arr = [7,1,7,1,7,1], d = 2
Output: 2

Example 5:

Input: arr = [66], d = 1
Output: 1

Constraints:

1 <= arr.length <= 1000
1 <= arr[i] <= 10^5
1 <= d <= arr.length

Solution: Recursion w/ Memoization

dp(i) = max{1, max{dp(j) + 1}}, if i can jump to j.
ans = max(dp(i))

Time complexity: O(n*d)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int maxJumps(vector<int>& a, int d) {

int n = a.size();

vector<int> m(n);

function<int(int)> dp = [&](int i) {

if (m[i]) return m[i];

int ans = 1;

for (int j = i + 1; j <= min(n - 1, i + d) && a[i] > a[j]; ++j)

ans = max(ans, dp(j) + 1);

for (int j = i - 1; j >= max(0, i - d) && a[i] > a[j]; --j)

ans = max(ans, dp(j) + 1);

return m[i] = ans;

};

int ans = 0;

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

ans = max(ans, dp(i));

return ans;

}

};

Solution 2: DP

Time complexity: O(nlogn + n*d)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int maxJumps(vector<int>& a, int d) {

const int n = a.size();

vector<pair<int, int>> m(n); // <height, index>

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

m[i] = {a[i], i};

// Solve from the lowest bar.

sort(begin(m), end(m));

vector<int> dp(n, 1);

for (auto [v, i] : m) {

for (int j = i + 1; j <= min(n - 1, i + d) && a[i] > a[j]; ++j)

dp[i] = max(dp[i], dp[j] + 1);

for (int j = i - 1; j >= max(0, i - d) && a[i] > a[j]; --j)

dp[i] = max(dp[i], dp[j] + 1);

}

return *max_element(begin(dp), end(dp));

}

};

Posts tagged as “hard”

花花酱 LeetCode 1354. Construct Target Array With Multiple Sums

Solution: Backwards Simulation

C++

花花酱 LeetCode 84. Largest Rectangle in Histogram

Solution 1: Monotonic Stack

C++

花花酱 LeetCode 1349. Maximum Students Taking Exam

Solution 1: DFS (TLE)

Solution 2: DP

C++

C++

花花酱 LeetCode 1345. Jump Game IV

Solution: HashTable + BFS

C++

Related Problems

花花酱 LeetCode 1344. Jump Game V

Solution: Recursion w/ Memoization

C++

Solution 2: DP

C++