Huahua’s Tech Road

花花酱 LeetCode 1743. Restore the Array From Adjacent Pairs

By zxi on January 30, 2021

There is an integer array nums that consists of n unique elements, but you have forgotten it. However, you do remember every pair of adjacent elements in nums.

You are given a 2D integer array adjacentPairs of size n - 1 where each adjacentPairs[i] = [u_i, v_i] indicates that the elements u_i and v_i are adjacent in nums.

It is guaranteed that every adjacent pair of elements nums[i] and nums[i+1] will exist in adjacentPairs, either as [nums[i], nums[i+1]] or [nums[i+1], nums[i]]. The pairs can appear in any order.

Return the original array nums. If there are multiple solutions, return any of them.

Example 1:

Input: adjacentPairs = [[2,1],[3,4],[3,2]]
Output: [1,2,3,4]
Explanation: This array has all its adjacent pairs in adjacentPairs.
Notice that adjacentPairs[i] may not be in left-to-right order.

Example 2:

Input: adjacentPairs = [[4,-2],[1,4],[-3,1]]
Output: [-2,4,1,-3]
Explanation: There can be negative numbers.
Another solution is [-3,1,4,-2], which would also be accepted.

Example 3:

Input: adjacentPairs = [[100000,-100000]]
Output: [100000,-100000]

Constraints:

nums.length == n
adjacentPairs.length == n - 1
adjacentPairs[i].length == 2
2 <= n <= 10⁵
-10⁵ <= nums[i], u_i, v_i <= 10⁵
There exists some nums that has adjacentPairs as its pairs.

Solution: Hashtable

Reverse thinking! For a given input array, e.g.
[1, 2, 3, 4, 5]
it’s adjacent pairs are [1,2] , [2,3], [3,4], [4,5]
all numbers appeared exactly twice except 1 and 5, since they are on the boundary.
We just need to find the head or tail of the input array, and construct the rest of the array in order.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> restoreArray(vector<vector<int>>& adjacentPairs) {

const int n = adjacentPairs.size() + 1;

unordered_map<int, vector<int>> g;

for (const auto& p : adjacentPairs) {

g[p[0]].push_back(p[1]);

g[p[1]].push_back(p[0]);

}

vector<int> ans(n);

for (const auto& [u, vs] : g)

if (vs.size() == 1) {

ans[0] = u;

ans[1] = vs[0];

break;

}

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

const auto& vs = g[ans[i - 1]];

ans[i] = vs[0] == ans[i - 2] ? vs[1] : vs[0];

}

return ans;

}

};

花花酱 LeetCode 1742. Maximum Number of Balls in a Box

By zxi on January 30, 2021

You are working in a ball factory where you have n balls numbered from lowLimit up to highLimit inclusive (i.e., n == highLimit - lowLimit + 1), and an infinite number of boxes numbered from 1 to infinity.

Your job at this factory is to put each ball in the box with a number equal to the sum of digits of the ball’s number. For example, the ball number 321 will be put in the box number 3 + 2 + 1 = 6 and the ball number 10 will be put in the box number 1 + 0 = 1.

Given two integers lowLimit and highLimit, return the number of balls in the box with the most balls.

Example 1:

Input: lowLimit = 1, highLimit = 10
Output: 2
Explanation:
Box Number:  1 2 3 4 5 6 7 8 9 10 11 ...
Ball Count:  2 1 1 1 1 1 1 1 1 0  0  ...
Box 1 has the most number of balls with 2 balls.

Example 2:

Input: lowLimit = 5, highLimit = 15
Output: 2
Explanation:
Box Number:  1 2 3 4 5 6 7 8 9 10 11 ...
Ball Count:  1 1 1 1 2 2 1 1 1 0  0  ...
Boxes 5 and 6 have the most number of balls with 2 balls in each.

Example 3:

Input: lowLimit = 19, highLimit = 28
Output: 2
Explanation:
Box Number:  1 2 3 4 5 6 7 8 9 10 11 12 ...
Ball Count:  0 1 1 1 1 1 1 1 1 2  0  0  ...
Box 10 has the most number of balls with 2 balls.

Constraints:

1 <= lowLimit <= highLimit <= 10⁵

Solution: Hashtable and base-10

Max sum will be 9+9+9+9+9 = 45

Time complexity: O((hi-lo) * log(hi))
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int countBalls(int lowLimit, int highLimit) {

vector<int> balls(46);

int ans = 0;

for (int i = lowLimit; i <= highLimit; ++i) {

int n = i;

int box = 0;

while (n) { box += n % 10; n /= 10; }

ans = max(ans, ++balls[box]);

}

return ans;

}

};

Python3

# Author: Huahua

class Solution:

def countBalls(self, lowLimit: int, highLimit: int) -> int:

balls = defaultdict(int)

ans = 0

for x in range(lowLimit, highLimit + 1):

s = sum(int(d) for d in str(x))

balls[s] += 1

ans = max(ans, balls[s])

return ans

花花酱 LeetCode 1739. Building Boxes

By zxi on January 23, 2021

You have a cubic storeroom where the width, length, and height of the room are all equal to n units. You are asked to place n boxes in this room where each box is a cube of unit side length. There are however some rules to placing the boxes:

You can place the boxes anywhere on the floor.
If box x is placed on top of the box y, then each side of the four vertical sides of the box y must either be adjacent to another box or to a wall.

Given an integer n, return the minimum possible number of boxes touching the floor.

Example 1:

Input: n = 3
Output: 3
Explanation: The figure above is for the placement of the three boxes.
These boxes are placed in the corner of the room, where the corner is on the left side.

Example 2:

Input: n = 4
Output: 3
Explanation: The figure above is for the placement of the four boxes.
These boxes are placed in the corner of the room, where the corner is on the left side.

Example 3:

Input: n = 10
Output: 6
Explanation: The figure above is for the placement of the ten boxes.
These boxes are placed in the corner of the room, where the corner is on the back side.

Constraints:

1 <= n <= 10⁹

Solution: Geometry

Step 1: Build a largest pyramid that has less then n cubes, whose base area is d*(d+1) / 2
Step 2: Build a largest triangle with cubes left, whose base area is l, l*(l + 1) / 2 >= left

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

C++

// Author: Huahua

class Solution {

public:

int minimumBoxes(int n) {

int d = 0;

int l = 0;

while (n - (d + 1) * (d + 2) / 2 > 0) {

n -= (d + 1) * (d + 2) / 2;

++d;

}

while (n > 0) n -= ++l;

return d * (d + 1) / 2 + l;

}

};

花花酱 LeetCode 1738. Find Kth Largest XOR Coordinate Value

By zxi on January 23, 2021

You are given a 2D matrix of size m x n, consisting of non-negative integers. You are also given an integer k.

The value of coordinate (a, b) of the matrix is the XOR of all matrix[i][j] where 0 <= i <= a < m and 0 <= j <= b < n (0-indexed).

Find the k^th largest value (1-indexed) of all the coordinates of matrix.

Example 1:

Input: matrix = [[5,2],[1,6]], k = 1
Output: 7
Explanation: The value of coordinate (0,1) is 5 XOR 2 = 7, which is the largest value.

Example 2:

Input: matrix = [[5,2],[1,6]], k = 2
Output: 5
Explanation: The value of coordinate (0,0) is 5 = 5, which is the 2nd largest value.

Example 3:

Input: matrix = [[5,2],[1,6]], k = 3
Output: 4
Explanation: The value of coordinate (1,0) is 5 XOR 1 = 4, which is the 3rd largest value.

Example 4:

Input: matrix = [[5,2],[1,6]], k = 4
Output: 0
Explanation: The value of coordinate (1,1) is 5 XOR 2 XOR 1 XOR 6 = 0, which is the 4th largest value.

Constraints:

m == matrix.length
n == matrix[i].length
1 <= m, n <= 1000
0 <= matrix[i][j] <= 10⁶
1 <= k <= m * n

Solution: DP

xor[i][j] = matrix[i][j] ^ xor[i – 1][j – 1] ^ xor[i – 1][j] ^ xor[i][j- 1]

Time complexity: O(mn)
Space complexity: O(mn)

C++

// Author: Huahua

class Solution {

public:

int kthLargestValue(vector<vector<int>>& matrix, int k) {

const int m = matrix.size(), n = matrix[0].size();

vector<int> v;

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

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

v.push_back(matrix[i][j]

^= (i ? matrix[i - 1][j] : 0)

^ (j ? matrix[i][j - 1] : 0)

^ (i * j ? matrix[i - 1][j - 1] : 0));

nth_element(begin(v), begin(v) + k - 1, end(v), greater<int>());

return v[k - 1];

}

};

花花酱 LeetCode 1737. Change Minimum Characters to Satisfy One of Three Conditions

By zxi on January 23, 2021

You are given two strings a and b that consist of lowercase letters. In one operation, you can change any character in a or b to any lowercase letter.

Your goal is to satisfy one of the following three conditions:

Every letter in a is strictly less than every letter in b in the alphabet.
Every letter in b is strictly less than every letter in a in the alphabet.
Both a and b consist of only one distinct letter.

Return the minimum number of operations needed to achieve your goal.

Example 1:

Input: a = "aba", b = "caa"
Output: 2
Explanation: Consider the best way to make each condition true:
1) Change b to "ccc" in 2 operations, then every letter in a is less than every letter in b.
2) Change a to "bbb" and b to "aaa" in 3 operations, then every letter in b is less than every letter in a.
3) Change a to "aaa" and b to "aaa" in 2 operations, then a and b consist of one distinct letter.
The best way was done in 2 operations (either condition 1 or condition 3).

Example 2:

Input: a = "dabadd", b = "cda"
Output: 3
Explanation: The best way is to make condition 1 true by changing b to "eee".

Constraints:

1 <= a.length, b.length <= 10⁵
a and b consist only of lowercase letters.

Solution: Brute Force

Time complexity: O(26*(m+n))
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int minCharacters(string a, string b) {

auto change = [](const string& a, const string& b) {

int ans = INT_MAX;

for (char c = 'a'; c < 'z'; ++c) {

int ops = 0;

for (char x : a) ops += x > c;

for (char x : b) ops += x <= c;

ans = min(ans, ops);

}

return ans;

};

int ans = min(change(a, b), change(b, a));

for (char c = 'a'; c <= 'z'; ++c) {

int ops = a.size() - count(begin(a), end(a), c) +

b.size() - count(begin(b), end(b), c);

ans = min(ans, ops);

}

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 1743. Restore the Array From Adjacent Pairs

Solution: Hashtable

C++

花花酱 LeetCode 1742. Maximum Number of Balls in a Box

Solution: Hashtable and base-10

C++

Python3

花花酱 LeetCode 1739. Building Boxes

Solution: Geometry

C++

花花酱 LeetCode 1738. Find Kth Largest XOR Coordinate Value

Solution: DP

C++

花花酱 LeetCode 1737. Change Minimum Characters to Satisfy One of Three Conditions

Solution: Brute Force

C++