Problem

Given an integer array num sorted in non-decreasing order.

You can perform the following operation any number of times:

  • Choose two indices, i and j, where nums[i] < nums[j].
  • Then, remove the elements at indices i and j from nums. The remaining elements retain their original order, and the array is re-indexed.

Return the minimum length of nums after applying the operation zero or more times.

Examples

Example 1

1
2
3
4
5
6
7
8


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

Output: 0

Explanation:

![](https://assets.leetcode.com/uploads/2024/05/18/tcase1.gif)

Example 2

1
2
3
4
5
6
7
8


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

Output: 0

Explanation:

![](https://assets.leetcode.com/uploads/2024/05/19/tcase2.gif)

Example 3

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


Input: nums = [1000000000,1000000000]

Output: 2

Explanation:

Since both numbers are equal, they cannot be removed.

#### Example 4

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

Output: 1

Explanation:

![](https://assets.leetcode.com/uploads/2024/05/19/tcase3.gif)

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9
  • nums is sorted in non-decreasing order.

Solution

Method 1 – Two Pointers + Greedy

Intuition

To minimize the array length, we want to remove as many pairs as possible where nums[i] < nums[j]. Since the array is sorted, we can use two pointers: one starting from the left and one from the right, and greedily pair the smallest with the largest possible.

Approach

  1. Initialize two pointers: left at 0, right at n-1.
  2. While left < right:
    • If nums[left] < nums[right], remove both and move left++, right–.
    • Else, move right– (since nums[left] >= nums[right], try next largest).
  3. Count the number of pairs removed.
  4. The minimum length is n - 2 * pairs.

Code

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

class Solution {
public:
    int minLengthAfterRemovals(vector<int>& nums) {
        int n = nums.size(), left = 0, right = n-1, pairs = 0;
        while (left < right) {
            if (nums[left] < nums[right]) {
                pairs++;
                left++;
                right--;
            } else {
                right--;
            }
        }
        return n - 2 * pairs;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func minLengthAfterRemovals(nums []int) int {
    n, left, right, pairs := len(nums), 0, len(nums)-1, 0
    for left < right {
        if nums[left] < nums[right] {
            pairs++
            left++
            right--
        } else {
            right--
        }
    }
    return n - 2*pairs
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public int minLengthAfterRemovals(int[] nums) {
        int n = nums.length, left = 0, right = n-1, pairs = 0;
        while (left < right) {
            if (nums[left] < nums[right]) {
                pairs++;
                left++;
                right--;
            } else {
                right--;
            }
        }
        return n - 2 * pairs;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    fun minLengthAfterRemovals(nums: IntArray): Int {
        var left = 0
        var right = nums.size - 1
        var pairs = 0
        while (left < right) {
            if (nums[left] < nums[right]) {
                pairs++
                left++
                right--
            } else {
                right--
            }
        }
        return nums.size - 2 * pairs
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def min_length_after_removals(nums: list[int]) -> int:
    n = len(nums)
    left, right = 0, n-1
    pairs = 0
    while left < right:
        if nums[left] < nums[right]:
            pairs += 1
            left += 1
            right -= 1
        else:
            right -= 1
    return n - 2 * pairs
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

impl Solution {
    pub fn min_length_after_removals(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let (mut left, mut right, mut pairs) = (0, n-1, 0);
        while left < right {
            if nums[left] < nums[right] {
                pairs += 1;
                left += 1;
                right -= 1;
            } else {
                right -= 1;
            }
        }
        (n - 2 * pairs) as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    minLengthAfterRemovals(nums: number[]): number {
        let left = 0, right = nums.length - 1, pairs = 0;
        while (left < right) {
            if (nums[left] < nums[right]) {
                pairs++;
                left++;
                right--;
            } else {
                right--;
            }
        }
        return nums.length - 2 * pairs;
    }
}

Complexity

  • ⏰ Time complexity: O(n)
    • Each element is processed at most once.
  • 🧺 Space complexity: O(1)
    • Only a few variables used.