Posts tagged as “greedy”

花花酱 LeetCode 1296. Divide Array in Sets of K Consecutive Numbers

By zxi on December 26, 2019

Given an array of integers nums and a positive integer k, find whether it’s possible to divide this array into sets of k consecutive numbers
Return True if its possibleotherwise return False.

Example 1:

Input: nums = [1,2,3,3,4,4,5,6], k = 4
Output: true
Explanation: Array can be divided into [1,2,3,4] and [3,4,5,6].

Example 2:

Input: nums = [3,2,1,2,3,4,3,4,5,9,10,11], k = 3
Output: true
Explanation: Array can be divided into [1,2,3] , [2,3,4] , [3,4,5] and [9,10,11].

Example 3:

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

Example 4:

Input: nums = [1,2,3,4], k = 3
Output: false
Explanation: Each array should be divided in subarrays of size 3.

Constraints:

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
1 <= k <= nums.length

Solution: BST + Greedy

Start from the smallest available number and find k consecutive numbers.

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

C++

// Author: Huahua

class Solution {

public:

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

if (nums.size() % k) return false;

map<int, int> m;

for (int num : nums) ++m[num];

while (m.size()) {

const int s = m.cbegin()->first;

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

auto it = m.find(s + i);

if (it == m.cend()) return false;

if (--it->second == 0) m.erase(it);

}

return true;

}

};

C++/V2

// Author: Huahua

class Solution {

public:

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

if (nums.size() % k) return false;

map<int, int> m;

for (int num : nums) ++m[num];

while (m.size()) {

auto it = m.begin();

const int s = it->first;

for (int i = 0; i < k; ++i, ++it) {

if (it->first != s + i) return false;

if (--it->second == 0) m.erase(it);

}

return true;

}

};

Solution 2: HashTable

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

C++

class Solution {

public:

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

if (nums.size() % k) return false;

unordered_map<int, int> m;

for (int num : nums) ++m[num];

queue<int> starts;

for (auto [n, f] : m)

if (!m.count(n - 1)) starts.push(n);

while (!starts.empty()) {

int s = starts.front();

starts.pop();

for (int t = s + k - 1; t >= s; t--) {

if (m[t] < m[s]) return false;

if ((m[t] -= m[s]) == 0) {

m.erase(t);

if (m.count(t + 1)) starts.push(t + 1);

}

return true;

}

};

花花酱 LeetCode 1266. Minimum Time Visiting All Points

By zxi on November 23, 2019

On a plane there are n points with integer coordinates points[i] = [xi, yi]. Your task is to find the minimum time in seconds to visit all points.

You can move according to the next rules:

In one second always you can either move vertically, horizontally by one unit or diagonally (it means to move one unit vertically and one unit horizontally in one second).
You have to visit the points in the same order as they appear in the array.

Example 1:

Input: points = [[1,1],[3,4],[-1,0]]
Output: 7
Explanation: One optimal path is [1,1] -> [2,2] -> [3,3] -> [3,4] -> [2,3] -> [1,2] -> [0,1] -> [-1,0]   
Time from [1,1] to [3,4] = 3 seconds 
Time from [3,4] to [-1,0] = 4 seconds
Total time = 7 seconds

Example 2:

Input: points = [[3,2],[-2,2]]
Output: 5

Constraints:

points.length == n
1 <= n <= 100
points[i].length == 2
-1000 <= points[i][0], points[i][1] <= 1000

Solution: Geometry + Greedy

dx = abs(x1 – x2)
dy = abs(y1 – y2)

go diagonally first for min(dx, dy) steps, and then go straight line for abs(dx – dy) steps.

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

C++

// Author: Huahua

class Solution {

public:

int minTimeToVisitAllPoints(vector<vector<int>>& points) {

int ans = 0;

for (size_t i = 1; i < points.size(); ++i) {

int dx = abs(points[i - 1][0] - points[i][0]);

int dy = abs(points[i - 1][1] - points[i][1]);

ans += min(dx, dy) + abs(dx - dy);

}

return ans;

}

};

花花酱 LeetCode 1253. Reconstruct a 2-Row Binary Matrix

By zxi on November 9, 2019

Given the following details of a matrix with n columns and 2 rows :

The matrix is a binary matrix, which means each element in the matrix can be 0 or 1.
The sum of elements of the 0-th(upper) row is given as upper.
The sum of elements of the 1-st(lower) row is given as lower.
The sum of elements in the i-th column(0-indexed) is colsum[i], where colsum is given as an integer array with length n.

Your task is to reconstruct the matrix with upper, lower and colsum.

Return it as a 2-D integer array.

If there are more than one valid solution, any of them will be accepted.

If no valid solution exists, return an empty 2-D array.

Example 1:

Input: upper = 2, lower = 1, colsum = [1,1,1]
Output: [[1,1,0],[0,0,1]]
Explanation: [[1,0,1],[0,1,0]], and [[0,1,1],[1,0,0]] are also correct answers.

Example 2:

Input: upper = 2, lower = 3, colsum = [2,2,1,1]
Output: []

Example 3:

Input: upper = 5, lower = 5, colsum = [2,1,2,0,1,0,1,2,0,1]
Output: [[1,1,1,0,1,0,0,1,0,0],[1,0,1,0,0,0,1,1,0,1]]

Constraints:

1 <= colsum.length <= 10^5
0 <= upper, lower <= colsum.length
0 <= colsum[i] <= 2

Solution: Greedy?

Two passes:
first pass, only process sum = 2, upper = 1, lower = 1
second pass, only process sum = 1, whoever has more leftover, assign 1 to that row.

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

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> reconstructMatrix(int upper, int lower, vector<int>& colsum) {

const int n = colsum.size();

vector<vector<int>> a(2, vector<int>(n));

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

if (colsum[i] == 2) {

a[0][i] = a[1][i] = 1;

--upper;

--lower;

}

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

if (colsum[i] == 1)

if (upper > lower) {

a[0][i] = 1;

--upper;

} else {

a[1][i] = 1;

--lower;

}

if (upper != 0 || lower != 0) return {};

return a;

}

};

花花酱 LeetCode 1221. Split a String in Balanced Strings

By zxi on October 13, 2019

Balanced strings are those who have equal quantity of ‘L’ and ‘R’ characters.

Given a balanced string s split it in the maximum amount of balanced strings.

Return the maximum amount of splitted balanced strings.

Example 1:

Input: s = "RLRRLLRLRL"
Output: 4
Explanation: s can be split into "RL", "RRLL", "RL", "RL", each substring contains same number of 'L' and 'R'.

Example 2:

Input: s = "RLLLLRRRLR"
Output: 3
Explanation: s can be split into "RL", "LLLRRR", "LR", each substring contains same number of 'L' and 'R'.

Example 3:

Input: s = "LLLLRRRR"
Output: 1
Explanation: s can be split into "LLLLRRRR".

Constraints:

1 <= s.length <= 1000
s[i] = 'L' or 'R'

Solution: Greedy

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

C++

// Author: Huahua

class Solution {

public:

int balancedStringSplit(string s) {

int b = 0;

int ans = 0;

for (char c : s) {

b += c == 'L' ? 1 : -1;

if (b == 0) ++ans;

}

return ans;

}

};

Posts tagged as “greedy”

花花酱 LeetCode 1296. Divide Array in Sets of K Consecutive Numbers

Solution: BST + Greedy

C++

C++/V2

Solution 2: HashTable

C++

Related Problems

花花酱 LeetCode 1282. Group the People Given the Group Size They Belong To

Solution: HashMap + Greedy

C++

花花酱 LeetCode 1266. Minimum Time Visiting All Points

C++

花花酱 LeetCode 1253. Reconstruct a 2-Row Binary Matrix

Solution: Greedy?

C++

花花酱 LeetCode 1221. Split a String in Balanced Strings

Solution: Greedy

C++