Janvier

1390. Four Divisors 2026.01.04

Given an integer array nums, return the sum of divisors of the integers in that array that have exactly four divisors. If there is no such integer in the array, return 0.

Example 1:

Input: nums = [21,4,7]
Output: 32
Explanation: 21 has 4 divisors: 1, 3, 7, 21
4 has 3 divisors: 1, 2, 4
7 has 2 divisors: 1, 7
The answer is the sum of divisors of 21 only.

Example 2:

Input: nums = [21,21]
Output: 64

Example 3:

Input: nums = [1,2,3,4,5]
Output: 0

Constraints:

  • 1 <= nums.length <= 10^4
  • 1 <= nums[i] <= 10^5

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
    def numDivisor(self, num: int) -> int:
        if abs(int(sqrt(num))-sqrt(num)) < 1e-9:
            return 0
        
        tot = 0
        count = 0
        for i in range(1, int(sqrt(num))+1):
            if num % i == 0:
                count += 2
                tot += i
                tot += num // i
            if count > 4:
                return 0

        return tot if count == 4 else 0

    def sumFourDivisors(self, nums: List[int]) -> int:
        res = 0
        for num in nums:
            res += self.numDivisor(num)
        
        return res

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
public:
    int sumFourDivisors(vector<int>& nums) {
        int res {0};
        for(int i: nums){
            res += numDivisor(i);
            cout << numDivisor(i) << endl;
        }
        return res;
    }
    int numDivisor(int num){
        int r = sqrt(num);
        if(r * r == num) return 0;

        int tot {0};
        int count {0};
        for(int i=1;i<sqrt(num);++i){
            if(num % i == 0){
                count += 2;
                if(count > 4) return 0;
                tot += i;
                tot += num / i;
            }
        }

        if(count == 4) return tot;
        else return 0;
    }
};

1975. Maximum Matrix Sum 2026.01.05

You are given an n x n integer matrix. You can do the following operation any number of times:

  • Choose any two adjacent elements of matrix and multiply each of them by -1.

Two elements are considered adjacent if and only if they share a border.

Your goal is to maximize the summation of the matrix’s elements. Return the maximum sum of the matrix’s elements using the operation mentioned above.

Example 1:

Input: matrix = [[1,-1],[-1,1]]
Output: 4
Explanation: We can follow the following steps to reach sum equals 4:

  • Multiply the 2 elements in the first row by -1.
  • Multiply the 2 elements in the first column by -1.

Example 2:

Input: matrix = [[1,2,3],[-1,-2,-3],[1,2,3]]
Output: 16
Explanation: We can follow the following step to reach sum equals 16:

  • Multiply the 2 last elements in the second row by -1.

Constraints:

  • n == matrix.length == matrix[i].length
  • 2 <= n <= 250
  • -105 <= matrix[i][j] <= 10^5

Solution

If the number of negative elements is even, we can always make it positive. If the number is odd, we can always choose the smallest absolute value to make it negative.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def maxMatrixSum(self, matrix: List[List[int]]) -> int:
        tot = 0
        minVal = 1e5+1
        count = 0

        n = len(matrix)

        for i in range(n):
            for j in range(n):
                minVal = min(minVal, abs(matrix[i][j]))
                tot += abs(matrix[i][j])
                if matrix[i][j] < 0:
                    count += 1
        
        return tot if (count % 2 == 0) else (tot - 2 * minVal)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    long long maxMatrixSum(vector<vector<int>>& matrix) {
        long long tot {0};
        int count {0};
        int minVal {INT_MAX};
        for(size_t i=0;i<matrix.size();++i){
            for(size_t j=0;j<matrix.size();++j){
                tot += abs(matrix[i][j]);
                minVal = min(minVal, abs(matrix[i][j]));
                if (matrix[i][j] < 0) count += 1;
            }
        }
        if(count % 2 == 0) return tot;
        else return tot - 2 * minVal;
    }
};

1161. Maximum Level Sum of a Binary Tree 2026.01.06

Given the root of a binary tree, the level of its root is 1, the level of its children is 2, and so on.

Return the smallest level x such that the sum of all the values of nodes at level x is maximal.

Example 1:

Input: root = [1,7,0,7,-8,null,null]
Output: 2
Explanation:
Level 1 sum = 1.
Level 2 sum = 7 + 0 = 7.
Level 3 sum = 7 + -8 = -1.
So we return the level with the maximum sum which is level 2.

Example 2:

Input: root = [989,null,10250,98693,-89388,null,null,null,-32127]
Output: 2

Constraints:

  • The number of nodes in the tree is in the range [1, 10^4].
  • -10^5 <= Node.val <= 10^5

Solution

Loop by hierarchy and compare

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxLevelSum(self, root: Optional[TreeNode]) -> int:
        curr_level = [root, ]
        max_sum = root.val
        max_level = 1
        level = 1

        while curr_level:
            next_level = list()
            curr_sum = 0

            for node in curr_level:
                curr_sum += node.val
                if node.left:
                    next_level.append(node.left)
                if node.right:
                    next_level.append(node.right)
                

            if curr_sum > max_sum:
                max_sum = curr_sum
                max_level = level

            curr_level = next_level
            level += 1
        return max_level

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxLevelSum(TreeNode* root) {
        int max_sum {root->val};
        int max_level {1};
        int level {1};
        vector<TreeNode*> curr_level {root};

        while(!curr_level.empty()){
            vector<TreeNode*> next_level;
            int curr_sum {0};
            for(TreeNode* node: curr_level){
                curr_sum += node->val;
                if(node->left) next_level.push_back(node->left);
                if(node->right) next_level.push_back(node->right);
            }
            if(curr_sum > max_sum){
                max_sum = curr_sum;
                max_level = level;
            }
            curr_level = move(next_level);
            level ++;
        }
        return max_level;
        
    }
};

Avril

3761. Minimum Absolute Distance Between Mirror Pairs 2026.04.17

You are given an integer array nums.

A mirror pair is a pair of indices (i, j) such that:

  • 0 <= i < j < nums.length, and
  • reverse(nums[i]) == nums[j], where reverse(x) denotes the integer formed by reversing the digits of x. Leading zeros are omitted after reversing, for example reverse(120) = 21.

Return the minimum absolute distance between the indices of any mirror pair. The absolute distance between indices i and j is abs(i - j).

If no mirror pair exists, return -1.

Example 1:

Input: nums = [12,21,45,33,54]

Output: 1

Explanation:

The mirror pairs are:

  • (0, 1) since reverse(nums[0]) = reverse(12) = 21 = nums[1], giving an absolute distance abs(0 - 1) = 1.
  • (2, 4) since reverse(nums[2]) = reverse(45) = 54 = nums[4], giving an absolute distance abs(2 - 4) = 2.

The minimum absolute distance among all pairs is 1.

Example 2:

Input: nums = [120,21]

Output: 1

Explanation:

There is only one mirror pair (0, 1) since reverse(nums[0]) = reverse(120) = 21 = nums[1].

The minimum absolute distance is 1.

Example 3:

Input: nums = [21,120]

Output: -1

Explanation:

There are no mirror pairs in the array.

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109​​​​​​​

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
public:
    int minMirrorPairDistance(vector<int>& nums) {
        unordered_map<int, int> mirror_pair;
        int min_dis = INT_MAX;

        for(int i = 0; i < nums.size(); ++i){
            if (mirror_pair.count(nums[i]) != 0){
              min_dis = min(min_dis, i - mirror_pair[nums[i]]);
            }
            mirror_pair[mirror(nums[i])] = i;
        }

        return min_dis == INT_MAX? -1 : min_dis;
    }
    int mirror(int num){
        int num1 = num;
        int res = 0;
        while(num){
            int r = num % 10;
            res = res * 10 + r;
            num = num / 10;
        }
        return res;
    }
};

1855. Maximum Distance Between a Pair of Values

You are given two non-increasing 0-indexed integer arrays nums1​​​​​​ and nums2​​​​​​.

A pair of indices (i, j), where 0 <= i < nums1.length and 0 <= j < nums2.length, is valid if both i <= j and nums1[i] <= nums2[j]. The distance of the pair is j - i​​​​.

Return the maximum distance of any valid pair (i, j). If there are no valid pairs, return 0.

An array arr is non-increasing if arr[i-1] >= arr[i] for every 1 <= i < arr.length.

Example 1:

Input: nums1 = [55,30,5,4,2], nums2 = [100,20,10,10,5] Output: 2 Explanation: The valid pairs are (0,0), (2,2), (2,3), (2,4), (3,3), (3,4), and (4,4). The maximum distance is 2 with pair (2,4).

Example 2:

Input: nums1 = [2,2,2], nums2 = [10,10,1]

Output: 1

Explanation: The valid pairs are (0,0), (0,1), and (1,1). The maximum distance is 1 with pair (0,1).

Example 3:

Input: nums1 = [30,29,19,5], nums2 = [25,25,25,25,25]

Output: 2

Explanation: The valid pairs are (2,2), (2,3), (2,4), (3,3), and (3,4). The maximum distance is 2 with pair (2,4).

Constraints:

  • 1 <= nums1.length, nums2.length <= 105
  • 1 <= nums1[i], nums2[j] <= 105
  • Both nums1 and nums2 are non-increasing.

Solutions

First try: $\mathcal{O}(mn)$ TLE

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
    int maxDistance(vector<int>& nums1, vector<int>& nums2) {
        int max_dis {0};
        for(int i = 0; i < nums1.size(); ++i){
          for(int j = i; j < nums2.size() && nums2[j] >= nums1[i]; ++j){
            max_dis = max(max_dis, j - i);
          }
        }
        return max_dis;
    }
};

Second try: $\mathcal{O}(m \log(n))$ optimzed with bisect method

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
    int maxDistance(vector<int>& nums1, vector<int>& nums2) {
        int max_dis {0};
        for(int i = 0; i < nums1.size(); ++i){
            auto it = upper_bound(nums2.begin(), nums2.end(), nums1[i], greater<int>());
            int idx = distance(nums2.begin(), it) - 1;
            max_dis = max(max_dis, idx - i);
        }
        return max_dis;
    }
};

Third try: $\mathcal{O}(m+n)$with two pointers

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int maxDistance(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size();
        int n = nums2.size();
        int j = 0;
        int max_dis = 0;
        for (int i = 0; i < m; ++i){
            if (j == n) {
                break;

            // j < n before second condition, otherwise it will cause
            // heap allocation overflow
            while (j < n && nums2[j] >= nums1[i]) ++j;
            max_dis = max(max_dis, j - i - 1);
          }
        return max_dis;
    }
};

2615. Sum of Distances 2026.04.23

You are given a 0-indexed integer array nums. There exists an array arr of length nums.length, where arr[i] is the sum of |i - j| over all j such that nums[j] == nums[i] and j != i. If there is no such j, set arr[i] to be 0.

Return the array arr.

Example 1:

Input: nums = [1,3,1,1,2]

Output: [5,0,3,4,0]

Explanation: When i = 0, nums[0] == nums[2] and nums[0] == nums[3]. Therefore, arr[0] = |0 - 2| + |0 - 3| = 5.
When i = 1, arr[1] = 0 because there is no other index with value 3.
When i = 2, nums[2] == nums[0] and nums[2] == nums[3]. Therefore, arr[2] = |2 - 0| + |2 - 3| = 3.
When i = 3, nums[3] == nums[0] and nums[3] == nums[2]. Therefore, arr[3] = |3 - 0| + |3 - 2| = 4.
When i = 4, arr[4] = 0 because there is no other index with value 2.

Example 2:

Input: nums = [0,5,3]

Output: [0,0,0]

Explanation: Since each element in nums is distinct, arr[i] = 0 for all i.

Constraints:

  • 1 <= nums.length <= 105
  • 0 <= nums[i] <= 109

Solution

First step, group the index of equal elements. Second step, use prefix sum from left to right and from right to left, each time an index moves right, left prefix sum add (num of elements on the left) * (diff between current element and left element), right prefix sum add (num of elements on the right) * (diff between right element and current element)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

class Solution {
public:
    vector<long long> distance(vector<int>& nums) {
      int n = nums.size();
      // get the index of each element
      unordered_map<int, vector<int>> idx_map;
      for(int i = 0; i < n; ++i){
        idx_map[nums[i]].push_back(i);
      }

      
      // evaluate distance sum for each element in idx_map
      unordered_map<int, vector<long long>> distance_sum;
      for(auto pair: idx_map){
        distance_sum[pair.first].assign(idx_map[pair.first].size() ,0);
        if(pair.second.size() >= 2){
          for(int i = 1; i < pair.second.size(); ++i){
            int diff = pair.second[i] - pair.second[i - 1];
            distance_sum[pair.first][i] = distance_sum[pair.first][i - 1] + diff * i;
          }

          long long prefix = 0;
          for(int i = pair.second.size() - 2; i >= 0; --i){
            int diff = pair.second[i + 1] - pair.second[i];
            prefix += diff * (idx_map[pair.first].size() - 1 - i);
            distance_sum[pair.first][i] += prefix;
          }
        }
      }


      // align index to distance sum
      unordered_map<int, long long> aligned_map;
      for (auto pair: idx_map){
        for (int i = 0; i < pair.second.size(); ++i){
          aligned_map[pair.second[i]] = distance_sum[pair.first][i];
        }
      }

      vector<long long> res;
      for (int i = 0; i < n; ++i){
        res.push_back(aligned_map[i]);
      }

      return res;
    }
};

1391. Check if There is a Valid Path in a Grid 2026.04.27

You are given an m x n grid. Each cell of 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 that 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).

Constraints:

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

Solution

Start from point [0, 0] with BFS. First check next available point, if it

  1. does not exceed the boundary
  2. has backward connectivity
  3. is not in current visited list (avoid loop) then append it to the queue.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

class Solution:
    def hasValidPath(self, grid: List[List[int]]) -> bool:
        n, m = len(grid), len(grid[0])
        q = deque()
        q.append([0, 0])
        visited = set()
        visited.add((0, 0))
        left = [0, -1]
        right = [0, 1]
        upper = [-1, 0]
        lower = [1, 0]
        state = {
            1: [left, right],
            2: [upper, lower],
            3: [left, lower],
            4: [right, lower],
            5: [left, upper],
            6: [right, upper],
        }

        while q:
            x, y = q.popleft()
            # print(f"x = {x}, y = {y}")
            # check if the end is reached
            if x == n - 1 and y == m - 1:
                return True

            moves = state[grid[x][y]]
            for move in moves:
                # print(move)
                dx, dy = move
                # print(f"dx={dx},dy={dy}")
                nx, ny = x + dx, y + dy
                # check if boundary is exceeded
                if nx < 0 or nx >= n or ny < 0 or ny >= m:
                    continue
                # print(f"nx = {nx}, ny = {ny}")
                # check backward connectivity
                if [-dx, -dy] in state[grid[nx][ny]] and (nx, ny) not in visited:
                    q.append([nx, ny])
                    visited.add((nx, ny))

        return False