Huahua’s Tech Road

花花酱 LeetCode 2121. Intervals Between Identical Elements

By zxi on December 26, 2021

You are given a 0-indexed array of n integers arr.

The interval between two elements in arr is defined as the absolute difference between their indices. More formally, the interval between arr[i] and arr[j] is |i - j|.

Return an array intervals of length n where intervals[i] is the sum of intervals between arr[i] and each element in arr with the same value as arr[i].

Note: |x| is the absolute value of x.

Example 1:

Input: arr = [2,1,3,1,2,3,3]
Output: [4,2,7,2,4,4,5]
Explanation:
- Index 0: Another 2 is found at index 4. |0 - 4| = 4
- Index 1: Another 1 is found at index 3. |1 - 3| = 2
- Index 2: Two more 3s are found at indices 5 and 6. |2 - 5| + |2 - 6| = 7
- Index 3: Another 1 is found at index 1. |3 - 1| = 2
- Index 4: Another 2 is found at index 0. |4 - 0| = 4
- Index 5: Two more 3s are found at indices 2 and 6. |5 - 2| + |5 - 6| = 4
- Index 6: Two more 3s are found at indices 2 and 5. |6 - 2| + |6 - 5| = 5

Example 2:

Input: arr = [10,5,10,10]
Output: [5,0,3,4]
Explanation:
- Index 0: Two more 10s are found at indices 2 and 3. |0 - 2| + |0 - 3| = 5
- Index 1: There is only one 5 in the array, so its sum of intervals to identical elements is 0.
- Index 2: Two more 10s are found at indices 0 and 3. |2 - 0| + |2 - 3| = 3
- Index 3: Two more 10s are found at indices 0 and 2. |3 - 0| + |3 - 2| = 4

Constraints:

n == arr.length
1 <= n <= 10⁵
1 <= arr[i] <= 10⁵

Solution: Math / Hashtable + Prefix Sum

For each arr[i], suppose it occurs in the array of total c times, among which k of them are in front of it and c – k – 1 of them are after it. Then the total sum intervals:
(i – j₁) + (i – j₂) + … + (i – j_k) + (j_k+1-i) + (j_k+2-i) + … + (j_c-i)
<=> k * i – sum(j₁~j_k) + sum(j_k+1~j_c) – (c – k – 1) * i

Use a hashtable to store the indies of each unique number in the array and compute the prefix sum for fast range sum query.

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

C++

// Author: Huahua

class Solution {

public:

vector<long long> getDistances(vector<int>& arr) {

const int n = arr.size();

unordered_map<int, vector<long long>> m;

vector<int> pos(n);

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

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

pos[i] = m[arr[i]].size() - 1;

}

for (auto& [k, idx] : m)

partial_sum(begin(idx), end(idx), begin(idx));

vector<long long> ans(n);

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

const auto& sums = m[arr[i]];

const long long k = pos[i];

const long long c = sums.size();

if (k > 0) ans[i] += k * i - sums[k - 1];

if (k + 1 < c) ans[i] += (sums[c - 1] - sums[k]) - (c - k - 1) * i;

}

return ans;

}

};

花花酱 LeetCode 2120. Execution of All Suffix Instructions Staying in a Grid

By zxi on December 26, 2021

There is an n x n grid, with the top-left cell at (0, 0) and the bottom-right cell at (n - 1, n - 1). You are given the integer n and an integer array startPos where startPos = [start_row, start_col] indicates that a robot is initially at cell (start_row, start_col).

You are also given a 0-indexed string s of length m where s[i] is the i^th instruction for the robot: 'L' (move left), 'R' (move right), 'U' (move up), and 'D' (move down).

The robot can begin executing from any i^th instruction in s. It executes the instructions one by one towards the end of s but it stops if either of these conditions is met:

The next instruction will move the robot off the grid.
There are no more instructions left to execute.

Return an array answer of length m where answer[i] is the number of instructions the robot can execute if the robot begins executing from the i^th instruction in s.

Example 1:

Input: n = 3, startPos = [0,1], s = "RRDDLU"
Output: [1,5,4,3,1,0]
Explanation: Starting from startPos and beginning execution from the i^th instruction:
- 0^th: "RRDDLU". Only one instruction "R" can be executed before it moves off the grid.
- 1^st:  "RDDLU". All five instructions can be executed while it stays in the grid and ends at (1, 1).
- 2^nd:   "DDLU". All four instructions can be executed while it stays in the grid and ends at (1, 0).
- 3^rd:    "DLU". All three instructions can be executed while it stays in the grid and ends at (0, 0).
- 4^th:     "LU". Only one instruction "L" can be executed before it moves off the grid.
- 5^th:      "U". If moving up, it would move off the grid.

Example 2:

Input: n = 2, startPos = [1,1], s = "LURD"
Output: [4,1,0,0]
Explanation:
- 0^th: "LURD".
- 1^st:  "URD".
- 2^nd:   "RD".
- 3^rd:    "D".

Example 3:

Input: n = 1, startPos = [0,0], s = "LRUD"
Output: [0,0,0,0]
Explanation: No matter which instruction the robot begins execution from, it would move off the grid.

Constraints:

m == s.length
1 <= n, m <= 500
startPos.length == 2
0 <= start_row, start_col < n
s consists of 'L', 'R', 'U', and 'D'.

Solution: Simulation

Time complexity: O(m²)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

vector<int> executeInstructions(int n, vector<int>& startPos, string s) {

const int m = s.length();

auto moves = [&](int k) -> int {

int x = startPos[1];

int y = startPos[0];

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

switch (s[i]) {

case 'R': x += 1; break;

case 'D': y += 1; break;

case 'L': x -= 1; break;

case 'U': y -= 1; break;

}

if (x < 0 || x == n || y < 0 || y == n)

return i - k;

}

return m - k;

};

vector<int> ans(m);

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

ans[i] = moves(i);

return ans;

}

};

花花酱 LeetCode 2119. A Number After a Double Reversal

By zxi on December 26, 2021

Reversing an integer means to reverse all its digits.

For example, reversing 2021 gives 1202. Reversing 12300 gives 321 as the leading zeros are not retained.

Given an integer num, reverse num to get reversed1, then reverse reversed1 to get reversed2. Return true if reversed2 equals num. Otherwise return false.

Example 1:

Input: num = 526
Output: true
Explanation: Reverse num to get 625, then reverse 625 to get 526, which equals num.

Example 2:

Input: num = 1800
Output: false
Explanation: Reverse num to get 81, then reverse 81 to get 18, which does not equal num.

Example 3:

Input: num = 0
Output: true
Explanation: Reverse num to get 0, then reverse 0 to get 0, which equals num.

Constraints:

0 <= num <= 10⁶

Solution: Math

The number must not end with 0 expect 0 itself.

e.g. 1230 => 321 => 123
e.g. 0 => 0 => 0

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

C++

// Author: Huahua

class Solution {

public:

bool isSameAfterReversals(int num) {

return num == 0 || num % 10;

}

};

花花酱 LeetCode 1922. Count Good Numbers

By zxi on December 25, 2021

A digit string is good if the digits (0-indexed) at even indices are even and the digits at odd indices are prime (2, 3, 5, or 7).

For example, "2582" is good because the digits (2 and 8) at even positions are even and the digits (5 and 2) at odd positions are prime. However, "3245" is not good because 3 is at an even index but is not even.

Given an integer n, return the total number of good digit strings of length n. Since the answer may be large, return it modulo 10⁹ + 7.

A digit string is a string consisting of digits 0 through 9 that may contain leading zeros.

Example 1:

Input: n = 1
Output: 5
Explanation: The good numbers of length 1 are "0", "2", "4", "6", "8".

Example 2:

Input: n = 4
Output: 400

Example 3:

Input: n = 50
Output: 564908303

Constraints:

1 <= n <= 10¹⁵

Solution: Fast Power

Easy to see that f(n) = (4 + (n & 1)) * f(n – 1), f(1) = 5

However, since n is huge, we need to rewrite f(n) as 4^n/2 * 5^(n+1)/2 and use fast power to compute it.

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

C++

// Author: Huahua

constexpr int kMod = 1e9 + 7;

long long modPow(long long base, long long n) {

long long ans = 1;

while (n) {

if (n & 1) ans = (ans * base) % kMod;

base = (base * base) % kMod;

n >>= 1;

}

return ans;

}

class Solution {

public:

int countGoodNumbers(long long n) {

return (modPow(4, n / 2) * modPow(5, (n + 1) / 2)) % kMod;

}

};

花花酱 LeetCode 1921. Eliminate Maximum Number of Monsters

By zxi on December 25, 2021

You are playing a video game where you are defending your city from a group of n monsters. You are given a 0-indexed integer array dist of size n, where dist[i] is the initial distance in kilometers of the i^th monster from the city.

The monsters walk toward the city at a constant speed. The speed of each monster is given to you in an integer array speed of size n, where speed[i] is the speed of the i^th monster in kilometers per minute.

You have a weapon that, once fully charged, can eliminate a single monster. However, the weapon takes one minute to charge.The weapon is fully charged at the very start.

You lose when any monster reaches your city. If a monster reaches the city at the exact moment the weapon is fully charged, it counts as a loss, and the game ends before you can use your weapon.

Return the maximum number of monsters that you can eliminate before you lose, or n if you can eliminate all the monsters before they reach the city.

Example 1:

Input: dist = [1,3,4], speed = [1,1,1]
Output: 3
Explanation:
In the beginning, the distances of the monsters are [1,3,4]. You eliminate the first monster.
After a minute, the distances of the monsters are [X,2,3]. You eliminate the second monster.
After a minute, the distances of the monsters are [X,X,2]. You eliminate the thrid monster.
All 3 monsters can be eliminated.

Example 2:

Input: dist = [1,1,2,3], speed = [1,1,1,1]
Output: 1
Explanation:
In the beginning, the distances of the monsters are [1,1,2,3]. You eliminate the first monster.
After a minute, the distances of the monsters are [X,0,1,2], so you lose.
You can only eliminate 1 monster.

Example 3:

Input: dist = [3,2,4], speed = [5,3,2]
Output: 1
Explanation:
In the beginning, the distances of the monsters are [3,2,4]. You eliminate the first monster.
After a minute, the distances of the monsters are [X,0,2], so you lose.
You can only eliminate 1 monster.

Constraints:

n == dist.length == speed.length
1 <= n <= 10⁵
1 <= dist[i], speed[i] <= 10⁵

Solution: Greedy

Sort by arrival time, and see how many we can eliminate.

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

C++

// Author: Huahua

class Solution {

public:

int eliminateMaximum(vector<int>& dist, vector<int>& speed) {

const int n = dist.size();

vector<int> t(n);

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

t[i] = (dist[i] + speed[i] - 1) / speed[i];

sort(begin(t), end(t));

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

if (t[i] <= i) return i;

return n;

}

};

Huahua's Tech Road

花花酱 LeetCode 2121. Intervals Between Identical Elements

Solution: Math / Hashtable + Prefix Sum

C++

花花酱 LeetCode 2120. Execution of All Suffix Instructions Staying in a Grid

Solution: Simulation

C++

花花酱 LeetCode 2119. A Number After a Double Reversal

Solution: Math

C++

花花酱 LeetCode 1922. Count Good Numbers

Solution: Fast Power

C++

花花酱 LeetCode 1921. Eliminate Maximum Number of Monsters

Solution: Greedy

C++