Huahua’s Tech Road

花花酱 LeetCode 1387. Sort Integers by The Power Value

By zxi on March 22, 2020

The power of an integer x is defined as the number of steps needed to transform x into 1 using the following steps:

if x is even then x = x / 2
if x is odd then x = 3 * x + 1

For example, the power of x = 3 is 7 because 3 needs 7 steps to become 1 (3 –> 10 –> 5 –> 16 –> 8 –> 4 –> 2 –> 1).

Given three integers lo, hi and k. The task is to sort all integers in the interval [lo, hi] by the power value in ascending order, if two or more integers have the same power value sort them by ascending order.

Return the k-th integer in the range [lo, hi] sorted by the power value.

Notice that for any integer x (lo <= x <= hi) it is guaranteed that x will transform into 1 using these steps and that the power of x is will fit in 32 bit signed integer.

Example 1:

Input: lo = 12, hi = 15, k = 2
Output: 13
Explanation: The power of 12 is 9 (12 --> 6 --> 3 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1)
The power of 13 is 9
The power of 14 is 17
The power of 15 is 17
The interval sorted by the power value [12,13,14,15]. For k = 2 answer is the second element which is 13.
Notice that 12 and 13 have the same power value and we sorted them in ascending order. Same for 14 and 15.

Example 2:

Input: lo = 1, hi = 1, k = 1
Output: 1

Example 3:

Input: lo = 7, hi = 11, k = 4
Output: 7
Explanation: The power array corresponding to the interval [7, 8, 9, 10, 11] is [16, 3, 19, 6, 14].
The interval sorted by power is [8, 10, 11, 7, 9].
The fourth number in the sorted array is 7.

Example 4:

Input: lo = 10, hi = 20, k = 5
Output: 13

Example 5:

Input: lo = 1, hi = 1000, k = 777
Output: 570

Constraints:

1 <= lo <= hi <= 1000
1 <= k <= hi - lo + 1

Solution: Precompute + quick select

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

C++

// Author: Huahua

class Solution {

public:

int getKth(int lo, int hi, int k) {

vector<pair<int, int>> vals;

for (int n = lo; n <= hi; ++n) {

int p = 0;

int x = n;

while (x != 1) {

if (x & 1) x = 3 * x + 1;

else x /= 2;

++p;

}

vals.emplace_back(p, n);

}

nth_element(begin(vals), begin(vals) + k - 1, end(vals));

return vals[k - 1].second;

}

};

花花酱 LeetCode 1391. Check if There is a Valid Path in a Grid

By zxi on March 22, 2020

Given a m x ngrid. Each cell of the grid represents a street. The street of grid[i][j] can be:

1 which means a street connecting the left cell and the right cell.
2 which means a street connecting the upper cell and the lower cell.
3 which means a street connecting the left cell and the lower cell.
4 which means a street connecting the right cell and the lower cell.
5 which means a street connecting the left cell and the upper cell.
6 which means a street connecting the right cell and the upper cell.

You will initially start at the street of the upper-left cell (0,0). A valid path in the grid is a path which starts from the upper left cell (0,0) and ends at the bottom-right cell (m - 1, n - 1). The path should only follow the streets.

Notice that you are not allowed to change any street.

Return true if there is a valid path in the grid or false otherwise.

Example 1:

Input: grid = [[2,4,3],[6,5,2]]
Output: true
Explanation: As shown you can start at cell (0, 0) and visit all the cells of the grid to reach (m - 1, n - 1).

Example 2:

Input: grid = [[1,2,1],[1,2,1]]
Output: false
Explanation: As shown you the street at cell (0, 0) is not connected with any street of any other cell and you will get stuck at cell (0, 0)

Example 3:

Input: grid = [[1,1,2]]
Output: false
Explanation: You will get stuck at cell (0, 1) and you cannot reach cell (0, 2).

Example 4:

Input: grid = [[1,1,1,1,1,1,3]]
Output: true

Example 5:

Input: grid = [[2],[2],[2],[2],[2],[2],[6]]
Output: true

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 300
1 <= grid[i][j] <= 6

Solution: BFS

Need to check both sides (x, y) -> (tx, ty) and (tx, ty) -> (x, y) to make sure a path exist.

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

C++

// Author: Huahua

class Solution {

public:

bool hasValidPath(vector<vector<int>>& grid) {

const int m = grid.size();

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

vector<int> dirs{0, -1, 0, 1, 0}; // [up, left, down, right]

vector<set<int>> rules{

{1, 3}, {0, 2}, {1, 2},

{2, 3}, {0, 1}, {0, 3}};

queue<int> q{{0}};

vector<int> seen(m * n);

seen[0] = 1;

while (!q.empty()) {

int cx = q.front() % n;

int cy = q.front() / n;

q.pop();

if (cx == n - 1 && cy == m - 1) return true;

for (int d : rules[grid[cy][cx] - 1]) {

int x = cx + dirs[d];

int y = cy + dirs[d + 1];

int key = y * n + x;

if (x < 0 || x >= n || y < 0 || y >= m || seen[key]

|| !rules[grid[y][x] - 1].count((d + 2) % 4)) continue;

seen[key] = 1;

q.push(key);

}

return false;

}

};

花花酱 LeetCode 1392. Longest Happy Prefix

By zxi on March 21, 2020

A string is called a happy prefix if is a non-empty prefix which is also a suffix (excluding itself).

Given a string s. Return the longest happy prefix of s .

Return an empty string if no such prefix exists.

Example 1:

Input: s = "level"
Output: "l"
Explanation: s contains 4 prefix excluding itself ("l", "le", "lev", "leve"), and suffix ("l", "el", "vel", "evel"). The largest prefix which is also suffix is given by "l".

Example 2:

Input: s = "ababab"
Output: "abab"
Explanation: "abab" is the largest prefix which is also suffix. They can overlap in the original string.

Example 3:

Input: s = "leetcodeleet"
Output: "leet"

Example 4:

Input: s = "a"
Output: ""

Constraints:

1 <= s.length <= 10^5
s contains only lowercase English letters.

Solution: Rolling Hash

Time complexity: O(n) / worst case: O(n^2)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

string longestPrefix(string_view s) {

const int kMod = 16769023;

const int kBase = 128;

const int n = s.length();

int p = 0;

int q = 0;

int a = 1;

int ans = 0;

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

p = (p + a * s[i - 1]) % kMod;

q = (q * kBase + s[n - i]) % kMod;

a = (a * kBase) % kMod;

if (p == q && s.substr(0, i) == s.substr(n - i))

ans = i;

}

return string(s.substr(0, ans));

}

};

花花酱 LeetCode 1385. Find the Distance Value Between Two Arrays

By zxi on March 21, 2020

Given two integer arrays arr1 and arr2, and the integer d, return the distance value between the two arrays.

The distance value is defined as the number of elements arr1[i] such that there is not any element arr2[j] where |arr1[i]-arr2[j]| <= d.

Example 1:

Input: arr1 = [4,5,8], arr2 = [10,9,1,8], d = 2
Output: 2
Explanation: 
For arr1[0]=4 we have: 
|4-10|=6 > d=2 
|4-9|=5 > d=2 
|4-1|=3 > d=2 
|4-8|=4 > d=2 
For arr1[1]=5 we have: 
|5-10|=5 > d=2 
|5-9|=4 > d=2 
|5-1|=4 > d=2 
|5-8|=3 > d=2
For arr1[2]=8 we have:
|8-10|=2 <= d=2
|8-9|=1 <= d=2
|8-1|=7 > d=2
|8-8|=0 <= d=2

Example 2:

Input: arr1 = [1,4,2,3], arr2 = [-4,-3,6,10,20,30], d = 3
Output: 2

Example 3:

Input: arr1 = [2,1,100,3], arr2 = [-5,-2,10,-3,7], d = 6
Output: 1

Constraints:

1 <= arr1.length, arr2.length <= 500
-10^3 <= arr1[i], arr2[j] <= 10^3
0 <= d <= 100

Solution 1: All pairs

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

C++

// Author: Huahua

class Solution {

public:

int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) {

int ans = 0;

for (int x : arr1) {

bool flag = true;

for (int y : arr2)

if (abs(x - y) <= d) {

flag = false;

break;

}

ans += flag;

}

return ans;

}

};

Python3

# Author: Huahua

class Solution:

def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:

return sum(all(abs(x - y) > d for y in arr2) for x in arr1)

Solution 2: Two Pointers

Sort arr1 in ascending order and sort arr2 in descending order.
Time complexity: O(mlogm + nlogn + m + n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) {

sort(begin(arr1), end(arr1));

sort(rbegin(arr2), rend(arr2));

int ans = 0;

for (int a : arr1) {

while (arr2.size() && arr2.back() < a - d)

arr2.pop_back();

ans += arr2.empty() || arr2.back() > a + d;

}

return ans;

}

};

Solution 3: Binary Search

Sort arr2 in ascending order. and do two binary searches for each element to determine the range of [a-d, a+d], if that range is empty we increase the counter

Time complexity: O(mlogm + nlogm)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) {

sort(begin(arr2), end(arr2));

int ans = 0;

for (int a : arr1) {

auto it1 = lower_bound(begin(arr2), end(arr2), a - d);

auto it2 = upper_bound(begin(arr2), end(arr2), a + d);

if (it1 == it2) ++ans;

}

return ans;

}

};

花花酱 LeetCode 1383. Maximum Performance of a Team

By zxi on March 21, 2020

There are n engineers numbered from 1 to n and two arrays: speed and efficiency, where speed[i] and efficiency[i] represent the speed and efficiency for the i-th engineer respectively. Return the maximum performance of a team composed of at most k engineers, since the answer can be a huge number, return this modulo 10^9 + 7.

The performance of a team is the sum of their engineers’ speeds multiplied by the minimum efficiency among their engineers.

Example 1:

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 2
Output: 60
Explanation: 
We have the maximum performance of the team by selecting engineer 2 (with speed=10 and efficiency=4) and engineer 5 (with speed=5 and efficiency=7). That is, performance = (10 + 5) * min(4, 7) = 60.

Example 2:

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 3
Output: 68
Explanation:
This is the same example as the first but k = 3. We can select engineer 1, engineer 2 and engineer 5 to get the maximum performance of the team. That is, performance = (2 + 10 + 5) * min(5, 4, 7) = 68.

Example 3:

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 4
Output: 72

Constraints:

1 <= n <= 10^5
speed.length == n
efficiency.length == n
1 <= speed[i] <= 10^5
1 <= efficiency[i] <= 10^8
1 <= k <= n

Solution: Greedy + Sliding Window

Sort engineers by their efficiency in descending order.
For each window of K engineers (we can have less than K people in the first k-1 windows), ans is sum(speed) * min(efficiency).

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

C++

// Author: Huahua

class Solution {

public:

int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) {

vector<pair<int, int>> es;

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

es.push_back({efficiency[i], speed[i]});

sort(rbegin(es), rend(es));

priority_queue<int, vector<int>, greater<int>> q;

long sum = 0;

long ans = 0;

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

if (i >= k) {

sum -= q.top();

q.pop();

}

sum += es[i].second;

q.push(es[i].second);

ans = max(ans, sum * es[i].first);

}

return ans % static_cast<int>(1e9 + 7);

}

};

Python3

# Author: Huahua

class Solution:

def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:

speeds = 0

ans = 0

q = []

for e, s in sorted(zip(efficiency, speed), reverse=True):

if len(q) >= k:

speeds -= heapq.heappop(q)

speeds += s

heapq.heappush(q, s)

ans = max(ans, speeds * e)

return ans % (10**9 + 7)

Huahua's Tech Road

花花酱 LeetCode 1387. Sort Integers by The Power Value

Solution: Precompute + quick select

C++

花花酱 LeetCode 1391. Check if There is a Valid Path in a Grid

Solution: BFS

C++

花花酱 LeetCode 1392. Longest Happy Prefix

Solution: Rolling Hash

C++

花花酱 LeetCode 1385. Find the Distance Value Between Two Arrays

Solution 1: All pairs

C++

Python3

Solution 2: Two Pointers

C++

Solution 3: Binary Search

C++

花花酱 LeetCode 1383. Maximum Performance of a Team

Solution: Greedy + Sliding Window

C++

Python3