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

June

2161. Partition Array According to Given Pivot 2026.06.08

You are given a 0-indexed integer array nums and an integer pivot. Rearrange nums such that the following conditions are satisfied:

  • Every element less than pivot appears before every element greater than pivot.
  • Every element equal to pivot appears in between the elements less than and greater than pivot.
  • The relative order of the elements less than pivot and the elements greater than pivot is maintained.
    • More formally, consider every pi, pj where pi is the new position of the ith element and pj is the new position of the jth element. If i < j and both elements are smaller (or larger) than pivot, then pi < pj.

Return nums after the rearrangement.

Example 1:

Input: nums = [9,12,5,10,14,3,10], pivot = 10
Output: [9,5,3,10,10,12,14]
Explanation:
The elements 9, 5, and 3 are less than the pivot so they are on the left side of the array. The elements 12 and 14 are greater than the pivot so they are on the right side of the array. The relative ordering of the elements less than and greater than pivot is also maintained. [9, 5, 3] and [12, 14] are the respective orderings.

Example 2:

Input: nums = [-3,4,3,2], pivot = 2
Output: [-3,2,4,3]
Explanation:
The element -3 is less than the pivot so it is on the left side of the array. The elements 4 and 3 are greater than the pivot so they are on the right side of the array. The relative ordering of the elements less than and greater than pivot is also maintained. [-3] and [4, 3] are the respective orderings.

Constraints:

  • 1 <= nums.length <= 10^5
  • -10^6 <= nums[i] <= 10^6
  • pivot equals to an element of nums.

Solution

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

class Solution {
public:
    vector<int> pivotArray(vector<int>& nums, int pivot) {
        vector<int> prv;
        vector<int> nxt;
        vector<int> mid;
        for (auto& num: nums) {
            if (num < pivot) {
                prv.push_back(num);
            } else if (num > pivot) {
                nxt.push_back(num);
            } else {
                mid.push_back(num);
            }
        }
        prv.insert(prv.end(), mid.begin(), mid.end());
        prv.insert(prv.end(), nxt.begin(), nxt.end());

        return prv;

    }
};

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

impl Solution {
    pub fn pivot_array(nums: Vec<i32>, pivot: i32) -> Vec<i32> {
        let mut prv = Vec::new();
        let mut mid = Vec::new();
        let mut nxt = Vec::new();
        for &num in &nums {
            if num < pivot {
                prv.push(num);
            } else if num > pivot {
                nxt.push(num);
            } else {
                mid.push(pivot);
            }
        }
        prv.append(&mut mid);
        prv.append(&mut nxt);
        prv
    }
}

Notes: concatenate vector in c++

1

vec1.insert(vec1.end(), vec2.begin(), vec2.end());

concatenate vector in rust

  1. append
1

vec1.append(&mut vec2);

append takes a mutable reference, and will move elements from vec2 to vec1. vec2 will be empty after the operation.

  1. extend
1

vec1.extend(&vec2);

vec2 will remain unchanged

  1. concat
1

let vec3 = vec![vec1, vec2].concat();

This will create a new element and keep vec1 and vec2

3689. Maximum Total Subarray Value I 2026.06.09

You are given an integer array nums of length n and an integer k.

You need to choose exactly k non-empty nums[l..r] of nums. Subarrays may overlap, and the exact same subarray (same l and r) can be chosen more than once.

The value of a subarray nums[l..r] is defined as: max(nums[l..r]) - min(nums[l..r]).

The total value is the sum of the values of all chosen subarrays.

Return the maximum possible total value you can achieve.

Example 1:

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

Output: 4

Explanation:

One optimal approach is:

  • Choose nums[0..1] = [1, 3]. The maximum is 3 and the minimum is 1, giving a value of 3 - 1 = 2.
  • Choose nums[0..2] = [1, 3, 2]. The maximum is still 3 and the minimum is still 1, so the value is also 3 - 1 = 2.

Adding these gives 2 + 2 = 4.

Example 2:

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

Output: 12

Explanation:

One optimal approach is:

  • Choose nums[0..3] = [4, 2, 5, 1]. The maximum is 5 and the minimum is 1, giving a value of 5 - 1 = 4.
  • Choose nums[0..3] = [4, 2, 5, 1]. The maximum is 5 and the minimum is 1, so the value is also 4.
  • Choose nums[2..3] = [5, 1]. The maximum is 5 and the minimum is 1, so the value is again 4.

Adding these gives 4 + 4 + 4 = 12.

Constraints:

  • 1 <= n == nums.length <= 5 * 10​​​​​​​^4
  • 0 <= nums[i] <= 10^9
  • 1 <= k <= 10^5

Solutions

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

impl Solution {
    pub fn max_total_value(nums: Vec<i32>, k: i32) -> i64 {
        let mut min_val = i32::MAX;
        let mut max_val = i32::MIN;
        for &num in &nums {
            min_val = min_val.min(num);
            max_val = max_val.max(num);
        }
        (max_val - min_val) as i64 * k as i64
    }
}

2130. Maximum Twin Sum of a Linked List 2026.06.14

In a linked list of size n, where n is even, the ith node (0-indexed) of the linked list is known as the twin of the (n-1-i)th node, if 0 <= i <= (n / 2) - 1.

  • For example, if n = 4, then node 0 is the twin of node 3, and node 1 is the twin of node 2. These are the only nodes with twins for n = 4.

The twin sum is defined as the sum of a node and its twin.

Given the head of a linked list with even length, return the maximum twin sum of the linked list.

Example 1:

Input: head = [5,4,2,1]
Output: 6
Explanation:
Nodes 0 and 1 are the twins of nodes 3 and 2, respectively. All have twin sum = 6.
There are no other nodes with twins in the linked list.
Thus, the maximum twin sum of the linked list is 6.

Example 2:

Input: head = [4,2,2,3]
Output: 7
Explanation:
The nodes with twins present in this linked list are:

  • Node 0 is the twin of node 3 having a twin sum of 4 + 3 = 7.
  • Node 1 is the twin of node 2 having a twin sum of 2 + 2 = 4.
    Thus, the maximum twin sum of the linked list is max(7, 4) = 7.

Example 3:

Input: head = [1,100000]
Output: 100001
Explanation:
There is only one node with a twin in the linked list having twin sum of 1 + 100000 = 100001.

Constraints:

  • The number of nodes in the list is an even integer in the range [2, 105].
  • 1 <= Node.val <= 105

Solutions

 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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    int pairSum(ListNode* head) {
        ListNode* curr = head;
        vector<int> nums;
        while(curr) {
            nums.push_back(curr->val);
            curr = curr->next;
        }
        int n = nums.size();
        int maxval = nums[0] + nums[n-1];
        for (int i = 1; i < n/2; ++i) {
            maxval = max(maxval, nums[i] + nums[n-1-i]);
        }
        return maxval;
        
        }
};

2095. Delete the Middle Node of a Linked List 2026.06.15

You are given the head of a linked list. Delete the middle node, and return the head of the modified linked list.

The middle node of a linked list of size n is the ⌊n / 2⌋th node from the start using 0-based indexing, where ⌊x⌋ denotes the largest integer less than or equal to x.

  • For n = 1, 2, 3, 4, and 5, the middle nodes are 0, 1, 1, 2, and 2, respectively.

Example 1:

Input: head = [1,3,4,7,1,2,6]
Output: [1,3,4,1,2,6]
Explanation:
The above figure represents the given linked list. The indices of the nodes are written below.
Since n = 7, node 3 with value 7 is the middle node, which is marked in red.
We return the new list after removing this node.

Example 2:

Input: head = [1,2,3,4]
Output: [1,2,4]
Explanation:
The above figure represents the given linked list.
For n = 4, node 2 with value 3 is the middle node, which is marked in red.

Example 3:

Input: head = [2,1]
Output: [2]
Explanation:
The above figure represents the given linked list.
For n = 2, node 1 with value 1 is the middle node, which is marked in red.
Node 0 with value 2 is the only node remaining after removing node 1.

Constraints:

  • The number of nodes in the list is in the range [1, 105].
  • 1 <= Node.val <= 105

Solution

  1. get the length of list first, then delete the middle one
 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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteMiddle(ListNode* head) {
        ListNode* curr = head;
        int cnt = 0;
        while(curr) {
            ++cnt;
            curr = curr -> next;
        }
        if(cnt == 1) return nullptr;

        curr = head;
        for(int i = 0; i < cnt / 2 - 1; ++i) {
            curr = curr -> next;
        }
        ListNode* mid = curr -> next;
        if(mid){
            ListNode* nxt = mid -> next;
            curr -> next = nxt;
        } else {
            curr -> next = nullptr;
        }
        return head;
    }
};
  1. Two pointers
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteMiddle(ListNode* head) {
        if (! head -> next) return nullptr;
        ListNode* slow = head;
        ListNode* fast = head -> next -> next;
        while (fast && fast -> next) {
            slow = slow -> next;
            fast = fast -> next -> next;
        }
        slow -> next = slow -> next -> next;
        return head;
    }
};