Leetcode Weekly Contest 436
Solutions for Weekly Contest 436
Problem1: Sort Matrix by Diagonals
In this problem, we need to sort the diagonals. First, we should sort the numbers of bottom-left matrix in the non-increasing order. To sort the diagonals, we can start the first index of each row. And then we can move row + 1, col + 1 to get all values in the same diagonal. After sorting the values, then reassign the values to the matrix with the same logic.
For the top-right matrix, we can start the first index of each column except for the first column. First column will be calculated in the bottom-left case. The logic is the same as the bottom-left case.
class Solution {
public:
vector<vector<int>> sortMatrix(vector<vector<int>>& grid) {
int n = grid.size();
// Sort diagonals in bottom-left (including middle diagonal) in non-increasing order
for (int i = n - 1; i >= 0; --i) {
int row = i, col = 0;
vector<int> diagonal;
// Extract diagonal elements
while (row < n && col < n) {
diagonal.push_back(grid[row][col]);
row++, col++;
}
// Sort in descending order
sort(diagonal.rbegin(), diagonal.rend());
// Put sorted values back into the matrix
row = i, col = 0;
for (int val : diagonal) {
grid[row++][col++] = val;
}
}
// Sort diagonals in top-right in non-decreasing order
for (int i = 1; i < n; ++i) {
int row = 0, col = i;
vector<int> diagonal;
// Extract diagonal elements
while (row < n && col < n) {
diagonal.push_back(grid[row][col]);
row++, col++;
}
// Sort in ascending order
sort(diagonal.begin(), diagonal.end());
// Put sorted values back into the matrix
row = 0, col = i;
for (int val : diagonal) {
grid[row++][col++] = val;
}
}
return grid;
}
};
Time Complexity Analysis
Extracting diagonals: O(n)per diagonal.
Sorting diagonals: O(nlogn) per diagonal.
Placing elements back: O(n) per diagonal.
There are approximately 2n−1 diagonals.
Thus, the total complexity is O(n2logn).
Problem2: Assign Elements to Groups with Constraints
In this problem, we should assign the divisible elements to the value in the groups. We cannot check all elements to all values because the number of groups and elements is 10^5. It should be TLE.
I remove the duplicated elements by choosing only earlier one. Also, I sorted the group values to reduce the search range after getting unique values. I can store the indexes of each value with the hashmap. When I should find the divisible values with the element, find the lower_bound from the distinct value array. This only cost O(logN).
To reduce the time complexity, I calculated the element value 1, because it will be applied to all groups by default.
class Solution {
public:
vector<int> assignElements(vector<int>& groups, vector<int>& elements) {
unordered_map<int, vector<int>> groupToIndices;
// Store indices of each group size
for (int i = 0; i < groups.size(); ++i) {
groupToIndices[groups[i]].push_back(i);
}
// Extract unique group sizes and sort them
vector<int> sortedGroups;
for (auto &entry : groupToIndices) {
sortedGroups.push_back(entry.first);
}
sort(sortedGroups.begin(), sortedGroups.end());
// Track the smallest index for each element in elements
unordered_map<int, int> elementIndex;
for (int i = elements.size() - 1; i >= 0; --i) {
elementIndex[elements[i]] = i; // Store the smallest index for each element
}
// Map to store the smallest valid element index for each group
unordered_map<int, int> bestAssignment;
// Iterate over each element and check its multiples in sortedGroups
for (auto &[element, index] : elementIndex) {
int multiple = element;
while (multiple > 1) {
auto it = lower_bound(sortedGroups.begin(), sortedGroups.end(), multiple);
if (it == sortedGroups.end()) break; // No more valid groups
if (*it == multiple && (bestAssignment.count(multiple) == 0 || bestAssignment[multiple] > index)) {
bestAssignment[*it] = index; // Store the smallest index
}
multiple += element;
}
}
// Initialize answer array with -1 (default unassigned state)
vector<int> result(groups.size(), -1);
// Special case: If '1' is present in elements, assign its index to all groups
if (elementIndex.count(1) > 0) {
fill(result.begin(), result.end(), elementIndex[1]);
}
// Assign best matching element indices to corresponding groups
for (auto &[groupSize, assignedIndex] : bestAssignment) {
for (auto &groupIndex : groupToIndices[groupSize]) {
if (result[groupIndex] == -1 || result[groupIndex] > assignedIndex) {
result[groupIndex] = assignedIndex;
}
}
}
return result;
}
};
Time Complexity Analysis
Sorting the unique group sizes: O(GlogG)(where G is the number of unique group sizes).
Traversing
elementsand populatingels: O(E)Checking divisibility using a sieve-like approach: O(ElogG).
Final assignment process: O(G).
Thus, the overall complexity is approximately O(ElogG+GlogG), which is efficient.
Problem3: Count Substrings Divisible By Last Digit
In this problem, we should find the substring that is divisible by the last digit. The string size is too long, so that we cannot check all substrings within the limited time.
In this case, we can only find the substring by calculating the remainder. Let’s say dp[i] means the number of substrings whose remainder is i in the current index. If we move to the next index, then every substring will become X * 10 + (next value). It means that every remainders should be recalculated by (X * 10 + next value) % divisor.
For example, if we divide the substring “124” by 3, then the remainder will be 1.
If the substring is “1243”, which is the 124 * 10 + 3, then the remainder will be (1 * 10 + 3) % 3 == 1. It means that If calculate the next remainder with current value x, then we can find the divisible substring counts with dp[0].
If the current value is the divisor, then we should add dp[0] to answer.
class Solution {
public:
long long countSubstrings(string s) {
long long totalCount = 0; // Stores the total valid substrings count
// Iterate over possible last digits (1 to 9)
for (int divisor = 1; divisor <= 9; ++divisor) {
vector<long long> dp(divisor, 0LL); // DP array to track remainders
// Iterate over the string to form substrings
for (char c : s) {
int currentDigit = c - '0'; // Convert char to int
vector<long long> newDP(divisor, 0LL); // Temporary DP array
// Update DP table for substrings ending at this digit
for (int remainder = 0; remainder < divisor; ++remainder) {
int newRemainder = (remainder * 10 + currentDigit) % divisor;
newDP[newRemainder] += dp[remainder]; // Carry forward counts
}
// Count single-digit substrings
newDP[currentDigit % divisor]++;
// Update DP table
dp = newDP;
// If the substring ending here is divisible by its last digit, count it
if (currentDigit == divisor) {
totalCount += dp[0];
}
}
}
return totalCount;
}
};
Time Complexity Analysis
Outer Loop: Iterate over digits 1 to 9 → O(9)=O(1) (constant).
Inner Loop: Traverse the string of length n → O(n).
Modular DP Update: Runs in O(9) time for each character.
Thus, the total complexity is O(n), which is optimal for this problem.
Problem4: Maximize the Minimum Game Score
In this problem, we should find the maximum of minimum possible value after, at most, m moves. In this problem, if you can make all points to K within m moves, then you can say that all points are over K-1, K-2, etc. So, we can simply check if random X is okay for the answer. If yes, we only need to check the values above X. Otherwise, check those below X.
Then, we need to solve the problem of whether it is possible to make all values larger than or equal to X if X is given. Now the X is given, we can calculate how many times we should visit every index.
cnt[i] = (X + points[i] -1) / points[i]
Now, we can visit the index i greedily. No matter how far you go from i, you should visit the current index(i) at cnt[i] times. In this problem you should visit all indexes to get back to the index i and every move counts. So, we just can visit the current cnt[i] times first, then we can go to the next index.
To visit index i, we can start from the previous index. [move i-1 to i]
And then, we should go to the next index and get back to the current as many times as needed. [move i to i+1 and move i+1 to i] * (cnt[i]-1 times).
We already visit once from the previous index, so we just need the cnt[i] - 1 times visit more.
In this case, we should reduce the cnt[i+1] by (cnt[i]-1).
If cnt[i] ==0 , even though we don’t need to visit more, then we need to move to i to visit the i+1 index.
However, if the cnt[i] == 0 and the i == n-1, which means that we don’t need any more visit after i, then we can stop moving.
class Solution {
public:
// Helper function to check if a given minimum value can be achieved
bool isPossible(vector<int>& points, long long targetValue, int maxMoves) {
int n = points.size();
vector<long long> requiredUpdates(n);
long long totalMoves = 0;
// Calculate how many times each index needs to be updated to reach targetValue
for (int i = 0; i < n; ++i) {
requiredUpdates[i] = (targetValue + points[i] - 1) / points[i]; // Ceiling division
// If previous index was updated, adjust current index accordingly
if (i > 0 && requiredUpdates[i - 1] > 0) {
totalMoves += 2 * requiredUpdates[i - 1] - 1;
requiredUpdates[i] = max(0LL, requiredUpdates[i] - (requiredUpdates[i - 1] - 1));
}
// Otherwise, if we are in the middle of the array, count a move
else if (i > 0 && i != n - 1) {
totalMoves++;
}
}
// Handle last index separately
if (requiredUpdates[n - 1] > 0) {
totalMoves += requiredUpdates[n - 1] * 2;
if (requiredUpdates[n - 2] > 0) {
totalMoves--; // Reduce one move if second last index was updated
}
}
return totalMoves <= maxMoves; // Check if we can achieve the target value within maxMoves
}
// Binary search to find the maximum possible minimum value
long long maxScore(vector<int>& points, int m) {
long long left = 1, right = 1e15, answer = 0;
while (left <= right) {
long long mid = left + (right - left) / 2;
// Check if it's possible to maintain a minimum score of 'mid'
if (isPossible(points, mid, m)) {
answer = mid; // Store the valid answer
left = mid + 1; // Try for a higher minimum value
} else {
right = mid - 1; // Reduce the search space
}
}
return answer; // Maximum minimum possible value
}
};
Time Complexity Analysis
Binary Search: Runs in O(log 1e15) ≈ O(50)
Greedy Checking Function (
pos): Iterates overnelements → O(n)Total Complexity: O(nlog1e15)≈ O(n⋅50) → O(n) in practical cases.