Quick Pointer Reference for the Five Problems#

About the Code Each problem provides implementations in C / C++ / JavaScript. The code is fully equivalent; switch tabs to view. The C version omits the return parameter management from LeetCode’s official signature that isn’t used here (such as returnColumnSizes), in order to focus on the pointer logic.

Problem Description#

Given an array nums arranged in non-strictly increasing order, in-place remove the duplicate elements so that each element appears only once, and return the new length of the array after removal. The relative order of the elements should be kept the same.

Since the array’s length cannot be changed in some languages, the result must be placed in the first part of the array nums. More formally, if there are k elements after removing duplicates, then the first k elements of nums should hold the final result. Return k; whatever is placed beyond position k doesn’t matter.

Example:

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

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

Constraints: 1 <= nums.length <= 3 * 10^4, -100 <= nums[i] <= 100, nums is sorted in non-decreasing order.

Approach: Fast-Slow Pointers Maintaining a “Deduplicated Prefix”#

A sorted array means equal elements must be adjacent. So we can divide the array into two segments:

• [0, slow]: the deduplicated result prefix, where nums[slow] is the last element in it;
• [fast, n-1]: the part not yet checked.

fast starts at 1 and scans rightward:

• If nums[fast] != nums[slow], it means a new value has been encountered (since duplicates are necessarily adjacent), so increment slow and write the new value to nums[slow];
• Otherwise, this value is the same as the last value already written, so skip it.

When the loop ends, slow is the index of the last element of the result, and the length is slow + 1.

Process Illustration#

Taking nums = [0,0,1,1,1,2,2,3,3,4] as an example:

1
Index   0  1  2  3  4  5  6  7  8  9
2
nums    0  0  1  1  1  2  2  3  3  4
3
        ↑  ↑
4
      slow fast
5

6
fast=1: nums[1]=0 == nums[0]=0  → duplicate, skip
7
fast=2: nums[2]=1 != nums[0]=0  → slow=1, nums[1]=1
8
fast=3: nums[3]=1 == nums[1]=1  → skip
9
fast=4: nums[4]=1 == nums[1]=1  → skip
10
fast=5: nums[5]=2 != nums[1]=1  → slow=2, nums[2]=2
11
fast=6: nums[6]=2 == nums[2]=2  → skip
12
fast=7: nums[7]=3 != nums[2]=2  → slow=3, nums[3]=3
13
fast=8: nums[8]=3 == nums[3]=3  → skip
14
fast=9: nums[9]=4 != nums[3]=3  → slow=4, nums[4]=4
15

16
Return slow + 1 = 5 → the first five positions of nums are [0,1,2,3,4] ✔

Code Implementation#

1
int removeDuplicates(int *nums, int numsSize) {
2
    if (numsSize == 0) return 0;
3

4
    int slow = 0;                        /* [0, slow] is the deduplicated prefix */
5
    for (int fast = 1; fast < numsSize; fast++) {
6
        if (nums[fast] != nums[slow]) {  /* new value found */
7
            slow++;
8
            nums[slow] = nums[fast];
9
        }
10
    }
11
    return slow + 1;                     /* length = last index + 1 */
12
}

1
#include <vector>
2
using namespace std;
3

4
class Solution {
5
public:
6
    int removeDuplicates(vector<int>& nums) {
7
        if (nums.empty()) return 0;
8

9
        int slow = 0;                       // [0, slow] is the deduplicated prefix
10
        for (int fast = 1; fast < (int)nums.size(); ++fast) {
11
            if (nums[fast] != nums[slow]) { // new value found
12
                ++slow;
13
                nums[slow] = nums[fast];
14
            }
15
        }
16
        return slow + 1;
17
    }
18
};

1
function removeDuplicates(nums) {
2
  if (nums.length === 0) return 0;
3

4
  let slow = 0;                        // [0, slow] is the deduplicated prefix
5
  for (let fast = 1; fast < nums.length; fast++) {
6
    if (nums[fast] !== nums[slow]) {   // new value found
7
      slow++;
8
      nums[slow] = nums[fast];
9
    }
10
  }
11
  return slow + 1;
12
}

Complexity#

Common Pitfalls#

1. Return slow + 1, not slow. slow is an index; the length needs a plus one. An empty array must return 0 separately, otherwise slow + 1 would return 1.
2. Compare against nums[slow], not nums[fast - 1]. Both give the same result for this problem, but using slow naturally generalizes to “each element may be kept at most k times.”
3. Don’t also move slow when a duplicate is found. slow only advances when a new value is written.

Extension: Keep Each Element at Most k Times (LeetCode 80)#

Change “compare with the previous written value” to “compare with the previous k written values,” and the template generalizes directly:

1
// Deduplicate a sorted array, keeping at most k copies of each element (k = 1 is this problem, k = 2 is LeetCode 80)
2
int removeDuplicatesAtMostK(vector<int>& nums, int k) {
3
    int slow = 0;
4
    for (int fast = 0; fast < (int)nums.size(); ++fast) {
5
        // When slow < k there are fewer than k elements, so write directly;
6
        // Otherwise, only when nums[fast] differs from "the value written k positions ago" does the (k+1)-th duplicate appear
7
        if (slow < k || nums[fast] != nums[slow - k]) nums[slow++] = nums[fast];
8
    }
9
    return slow;
10
}

Problem Description#

A phrase is considered a palindrome if, after converting all uppercase characters to lowercase and removing all non-alphanumeric characters, it reads the same forward and backward. Letters and digits are both alphanumeric characters.

Given a string s, return true if it is a palindrome; otherwise, return false.

Example:

1
Input: s = "A man, a plan, a canal: Panama"
2
Output: true
3
Explanation: "amanaplanacanalpanama" is a palindrome
4

5
Input: s = "race a car"
6
Output: false
7
Explanation: "raceacar" is not a palindrome
8

9
Input: s = " "
10
Output: true
11
Explanation: After removing non-alphanumeric characters, an empty string "" is obtained, and an empty string reads the same forwards and backwards

Constraints: 1 <= s.length <= 2 * 10^5, s consists only of printable ASCII characters.

Approach: Two Pointers Skipping “Invalid Characters”#

If in-place operation is not allowed, the most intuitive approach is to first filter the string into pure alphanumeric characters, then reverse and compare—but that requires O(n) extra space.

The definition of a palindrome only cares about whether the two ends are symmetric, so using two pointers converging from both ends toward the middle is sufficient: i moves from left to right, j moves from right to left, each skipping non-alphanumeric characters, then comparing the two positions (converting to lowercase uniformly).

Only one pass is needed, and no new string needs to be constructed.

Process Illustration#

1
s = "A man, a plan, a canal: Panama"
2
     i                           j
3

4
i='A', j='a' → both lowercase to 'a', equal → i++, j--
5

6
When i advances, skip ' ', ',' → 'm'; when j moves back, skip 'l', 'a', etc. …… compare pair by pair
7
……
8

9
Finally i >= j, all symmetric → true ✔
10

11
Counterexample "race a car":
12
i='r', j='r' equal → i='a', j='a' equal → i='c', j='c' equal
13
→ i='e' skip space, j='a' → 'e' != 'a' → false ✘

Code Implementation#

1
#include <ctype.h>
2
#include <string.h>
3

4
int isPalindrome(char *s) {
5
    int i = 0;
6
    int j = (int)strlen(s) - 1;
7

8
    while (i < j) {
9
        /* Skip non-alphanumeric characters; note the inner loop must also check i < j */
10
        while (i < j && !isalnum((unsigned char)s[i])) i++;
11
        while (i < j && !isalnum((unsigned char)s[j])) j--;
12

13
        if (tolower((unsigned char)s[i]) != tolower((unsigned char)s[j])) return 0; /* false */
14
        i++;
15
        j--;
16
    }
17
    return 1; /* true */
18
}

1
#include <cctype>
2
#include <string>
3
using namespace std;
4

5
class Solution {
6
public:
7
    bool isPalindrome(string s) {
8
        int i = 0;
9
        int j = (int)s.size() - 1;
10

11
        while (i < j) {
12
            // Skip non-alphanumeric characters; note the inner loop must also check i < j
13
            while (i < j && !isalnum((unsigned char)s[i])) ++i;
14
            while (i < j && !isalnum((unsigned char)s[j])) --j;
15

16
            if (tolower((unsigned char)s[i]) != tolower((unsigned char)s[j])) return false;
17
            ++i;
18
            --j;
19
        }
20
        return true;
21
    }
22
};

1
function isPalindrome(s) {
2
  const isAlnum = (ch) => /[0-9a-zA-Z]/.test(ch);
3

4
  let i = 0;
5
  let j = s.length - 1;
6

7
  while (i < j) {
8
    // Skip non-alphanumeric characters; note the inner loop must also check i < j
9
    while (i < j && !isAlnum(s[i])) i++;
10
    while (i < j && !isAlnum(s[j])) j--;
11

12
    if (s[i].toLowerCase() !== s[j].toLowerCase()) return false;
13
    i++;
14
    j--;
15
  }
16
  return true;
17
}

Complexity#

Common Pitfalls#

1. The inner while must include i < j. Otherwise, when the entire string consists of non-alphanumeric characters (such as " ", "...."), i will keep advancing past j, and j will retreat past -1, with both sides reading and writing outside the array bounds—in C this is undefined behavior, and running with AddressSanitizer will directly report stack-buffer-overflow.
2. C / C++ isalnum, tolower parameters must be cast to unsigned char. These two functions accept int and require values that are unsigned char or EOF; when passing char directly, if the character byte is negative (which is the case for subsequent bytes of UTF-8 multi-byte characters), it is undefined behavior.
3. "0P" is false, "0P0" is true. Digits must also participate in the comparison; don’t only check for letters.
4. Both " " and "" return true. The loop condition i < j ensures that an empty string or a single character is directly judged as successful.

Problem Description#

Given an array nums of n elements containing red, white, and blue, sort them in-place so that elements of the same color are adjacent, arranged in the order red, white, and blue. We use the integers 0, 1, and 2 to represent red, white, and blue respectively.

You must solve this problem without using the library’s built-in sort function.

Example:

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

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

Constraints: n == nums.length, 1 <= n <= 300, nums[i] is 0, 1, or 2.

Follow-up: Could you come up with a one-pass algorithm using only constant extra space?

Approach: Dutch National Flag Problem, Three Pointers#

There are only three possible values, so no real sorting is needed—just partition the elements into three regions. Use three pointers to maintain three zones:

1
[0, p0)  all 0s        p0: the position where the next 0 should go
2
[p0, i)  all 1s        i : the position currently being checked
3
[i, p2]  not yet processed      p2: the position where the next 2 should go
4
(p2, n)  all 2s

At each step, look at nums[i] (the leftmost element of the “unprocessed region”):

• nums[i] == 0: It belongs on the left, so swap it with nums[p0]. After the swap, position p0 becomes 0, and p0 moves right by one; the element swapped into position i is the original nums[p0]—since the [p0, i) range is all 1s, the swapped-in element can only be 0 or 1, its placement is already determined, so i can also move right.
• nums[i] == 2: It belongs on the right, so swap it with nums[p2]. The element swapped into position i is taken from the tail of the unprocessed region, which hasn’t been examined yet, so p2 moves left by one but i stays put, and the next iteration re-examines this position.
• nums[i] == 1: It already belongs in the middle, so i simply moves right.

When i > p2, the unprocessed region is empty and sorting is complete.

Walkthrough Diagram#

Using nums = [2,0,2,1,1,0] as an example:

1
Initial: p0=0  i=0                    p2=5
2
nums   [2, 0, 2, 1, 1, 0]
3

4
i=0: nums[0]=2 → swap with nums[5]=0 → p2=4
5
nums   [0, 0, 2, 1, 1, 2]
6
i=0: nums[0]=0 → swap with nums[0] (in place) → p0=1, i=1
7
nums   [0, 0, 2, 1, 1, 2]
8
i=1: nums[1]=0 → swap with nums[1] (in place) → p0=2, i=2
9
nums   [0, 0, 2, 1, 1, 2]
10
i=2: nums[2]=2 → swap with nums[4]=1 → p2=3 (i does not move!)
11
nums   [0, 0, 1, 1, 2, 2]
12
i=2: nums[2]=1 → i=3
13
i=3: nums[3]=1 → i=4
14
i=4 > p2=3 → end ✔

Code Implementation#

1
static void swapInt(int *a, int *b) {
2
    int t = *a;
3
    *a = *b;
4
    *b = t;
5
}
6

7
void sortColors(int *nums, int numsSize) {
8
    int p0 = 0;                   /* position for the next 0 */
9
    int i = 0;                    /* current scan position */
10
    int p2 = numsSize - 1;        /* position for the next 2 */
11

12
    while (i <= p2) {
13
        if (nums[i] == 0) {
14
            swapInt(&nums[i], &nums[p0]);
15
            p0++;
16
            i++;                  /* what was swapped in must be 0 or 1, so we can skip */
17
        } else if (nums[i] == 2) {
18
            swapInt(&nums[i], &nums[p2]);
19
            p2--;                 /* what was swapped in is an unprocessed element, i cannot advance */
20
        } else {
21
            i++;                  /* 1 stays in place */
22
        }
23
    }
24
}

1
#include <vector>
2
using namespace std;
3

4
class Solution {
5
public:
6
    void sortColors(vector<int>& nums) {
7
        int p0 = 0;                          // position for the next 0
8
        int i = 0;                           // current scan position
9
        int p2 = (int)nums.size() - 1;       // position for the next 2
10

11
        while (i <= p2) {
12
            if (nums[i] == 0) {
13
                swap(nums[i], nums[p0]);
14
                ++p0;
15
                ++i;                         // what was swapped in must be 0 or 1
16
            } else if (nums[i] == 2) {
17
                swap(nums[i], nums[p2]);
18
                --p2;                        // what was swapped in is an unprocessed element, i cannot advance
19
            } else {
20
                ++i;                         // 1 stays in place
21
            }
22
        }
23
    }
24
};

1
function sortColors(nums) {
2
  let p0 = 0;                  // position for the next 0
3
  let i = 0;                   // current scan position
4
  let p2 = nums.length - 1;    // position for the next 2
5

6
  while (i <= p2) {
7
    if (nums[i] === 0) {
8
      [nums[i], nums[p0]] = [nums[p0], nums[i]];
9
      p0++;
10
      i++;                     // what was swapped in must be 0 or 1, so we can skip
11
    } else if (nums[i] === 2) {
12
      [nums[i], nums[p2]] = [nums[p2], nums[i]];
13
      p2--;                    // what was swapped in is an unprocessed element, i cannot advance
14
    } else {
15
      i++;                     // 1 stays in place
16
    }
17
  }
18
}

Complexity#

Common Pitfalls#

1. After handling a 2, i must absolutely not advance. The element swapped in from the tail hasn’t been examined yet—it could be a 0. This is the easiest place to make a mistake in this problem.
2. The loop condition must be i <= p2, not i < p2. When i == p2, that position still holds an unprocessed element and must still be checked. Writing i < p2 will skip a middle element: for example, nums = [1,0,2,0,1], the correct result is [0,0,1,1,2], but i < p2 will output [0,1,1,0,2].
3. Don’t take the shortcut of “two-pass counting sort.” Counting the number of 0s/1s/2s and then filling them back in is also O(n) time and O(1) space, but it requires two passes and doesn’t demonstrate the pointer-partitioning idea.

Problem Description#

You are given two integer arrays nums1 and nums2 arranged in non-decreasing order, along with two integers m and n, which represent the number of elements in nums1 and nums2 respectively.

Please merge nums2 into nums1 so that the merged array is also arranged in non-decreasing order.

Note: The final merged array should not be returned by the function, but stored in array nums1. To accommodate this, the initial length of nums1 is m + n, where the first m elements represent the elements to be merged, and the last n elements are 0 (placeholders) that should be ignored.

Example:

1
Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
2
Output: [1,2,2,3,5,6]
3

4
Input: nums1 = [1], m = 1, nums2 = [], n = 0
5
Output: [1]

Constraints: nums1.length == m + n, nums2.length == n, 0 <= m, n <= 200.

Approach: Write from Back to Front, Not Front to Back#

If you merge from front to back, the first nums2 element written into nums1[0] will overwrite nums1 elements that haven’t been processed yet, unless you first move all of nums1 elsewhere (which degrades to O(m+n) extra space).

But notice that the last n positions of nums1 are already empty! So reverse the direction: fill from the end of the array backward, each time taking the larger of nums1 and nums2’s remaining parts and placing it at the rightmost position. At this point:

• The write position tail is always to the right of p1 and p2, writing into empty slots that have already been read, so it’s impossible to overwrite unprocessed elements;
• When nums2 has been fully moved (p2 < 0), the loop ends — at this point the remaining elements of nums1 are already in their correct positions and don’t need to be touched.

Process Diagram#

1
nums1 = [1,2,3,0,0,0]  m=3      nums2 = [2,5,6]  n=3
2
          p1=2   tail=5                    p2=2
3

4
Compare nums1[2]=3 with nums2[2]=6 → 6 is larger → nums1[5]=6, p2=1, tail=4
5
          [1,2,3,0,0,6]
6
Compare 3 with nums2[1]=5 → 5 is larger → nums1[4]=5, p2=0, tail=3
7
          [1,2,3,0,5,6]
8
Compare 3 with nums2[0]=2 → 3 is larger → nums1[3]=3, p1=1, tail=2
9
          [1,2,3,3,5,6]
10
Compare nums1[1]=2 with 2 → equal, take nums2 → nums1[2]=2, p2=-1, tail=1
11
          [1,2,2,3,5,6]
12
p2 < 0 → end, the first m+n positions of nums1 are the answer ✔

Code Implementation#

1
void merge(int *nums1, int m, int *nums2, int n) {
2
    int p1 = m - 1;               /* last element to be merged in nums1 */
3
    int p2 = n - 1;               /* last element to be merged in nums2 */
4
    int tail = m + n - 1;         /* write position, from back to front */
5

6
    while (p2 >= 0) {
7
        /* p1 may already be -1, so we must check p1 >= 0 first (using && short-circuit) */
8
        if (p1 >= 0 && nums1[p1] > nums2[p2]) {
9
            nums1[tail--] = nums1[p1--];
10
        } else {
11
            nums1[tail--] = nums2[p2--];
12
        }
13
    }
14
}

1
#include <vector>
2
using namespace std;
3

4
class Solution {
5
public:
6
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
7
        int p1 = m - 1;                       // last element to be merged in nums1
8
        int p2 = n - 1;                       // last element to be merged in nums2
9
        int tail = m + n - 1;                 // write position, from back to front
10

11
        while (p2 >= 0) {
12
            // p1 may already be -1, so we must check p1 >= 0 first (using && short-circuit) */
13
            if (p1 >= 0 && nums1[p1] > nums2[p2]) {
14
                nums1[tail--] = nums1[p1--];
15
            } else {
16
                nums1[tail--] = nums2[p2--];
17
            }
18
        }
19
    }
20
};

1
function merge(nums1, m, nums2, n) {
2
  let p1 = m - 1;              // last element to be merged in nums1
3
  let p2 = n - 1;              // last element to be merged in nums2
4
  let tail = m + n - 1;        // write position, from back to front
5

6
  while (p2 >= 0) {
7
    // p1 may already be -1, so we must check p1 >= 0 first (using && short-circuit) */
8
    if (p1 >= 0 && nums1[p1] > nums2[p2]) {
9
      nums1[tail--] = nums1[p1--];
10
    } else {
11
      nums1[tail--] = nums2[p2--];
12
    }
13
  }
14
}

Complexity#

Common Pitfalls#

1. p1 >= 0 must be written before nums1[p1] > nums2[p2]. Rely on &&’s short-circuit evaluation to prevent out-of-bounds access to nums1[-1].
2. The loop condition can only be p2 >= 0. Don’t write it as p1 >= 0 && p2 >= 0: when nums2 is exhausted first, the remaining elements of nums1 are already in their correct positions and it’s indeed safe to stop; but when nums1 is exhausted first, you must continue moving the remaining elements of nums2 over (at this point nums1[p1] doesn’t exist, and the p1 >= 0 branch automatically takes else).
3. Boundary cases of m = 0 or n = 0. When n = 0, the loop doesn’t execute even once, and nums1 is returned as-is; when m = 0, all elements are taken from nums2.
4. Don’t first copy nums2 to the tail of nums1 and then sort. That discards the premise that “both arrays are individually sorted,” degrading the time to O((m+n)log(m+n)).

Problem Description#

Given an integer array nums sorted in non-decreasing order, return a new array consisting of the squares of each number, also sorted in non-decreasing order.

Example:

1
Input: nums = [-4,-1,0,3,10]
2
Output: [0,1,9,16,100]
3
Explanation: After squaring, we get [16,1,0,9,100], and after sorting, it becomes [0,1,9,16,100]
4

5
Input: nums = [-7,-3,2,3,11]
6
Output: [4,9,9,49,121]

Constraints: 1 <= nums.length <= 10^4, -10^4 <= nums[i] <= 10^4, nums is sorted in non-decreasing order.

Approach: The Maximum Value Can Only Appear at Either End#

When the array contains negative numbers, the order after squaring no longer matches the original order — -4 is to the left of -1, but after squaring 16 > 1. However, there is a key property:

The maximum value after squaring must come from either the leftmost end of the array (the negative number with the largest absolute value) or the rightmost end (the largest positive number); it cannot come from the middle.

Because nums is monotonically increasing, |nums[i]| is monotonically decreasing on the left half and monotonically increasing on the right half, so the maximum value of |nums[i]| must be at one of the two ends of the interval.

Therefore, we can generate the result from largest to smallest: use two pointers i and j pointing to the two ends respectively, compare nums[i]² with nums[j]² each time, fill the larger one into the end of the result array, then move the corresponding pointer inward. Filling from back to front this way, the final result is in ascending order.

Process Illustration#

1
nums = [-4,-1,0,3,10]             res = [ , , , , ]
2
        i          j
3
        16   vs   100   → 100 is larger → res[4]=100, j=3
4
[-4,-1,0,3,10]                    res = [ , , , ,100]
5
  i     j
6
   16  vs  9         → 16 is larger  → res[3]=16,  i=1
7
[-4,-1,0,3,10]                    res = [ , , ,16,100]
8
     i  j
9
    1  vs  9         → 9 is larger   → res[2]=9,   j=2
10
[-4,-1,0,3,10]                    res = [ , ,9,16,100]
11
     i=j
12
    0  vs  0         → i == j, take 0 → res[0]=0
13

14
res = [0,1,9,16,100] ✔

Code Implementation#

1
#include <stdlib.h>
2

3
int *sortedSquares(int *nums, int numsSize, int *returnSize) {
4
    int *res = (int *)malloc(sizeof(int) * numsSize);
5
    int i = 0;
6
    int j = numsSize - 1;
7
    int k = numsSize - 1;         /* fill from the end of the result array backwards */
8

9
    while (i <= j) {
10
        int left = nums[i] * nums[i];
11
        int right = nums[j] * nums[j];
12
        if (left > right) {
13
            res[k--] = left;
14
            i++;
15
        } else {
16
            res[k--] = right;
17
            j--;
18
        }
19
    }
20

21
    *returnSize = numsSize;
22
    return res;
23
}

1
#include <cmath>
2
#include <vector>
3
using namespace std;
4

5
class Solution {
6
public:
7
    vector<int> sortedSquares(vector<int>& nums) {
8
        int n = (int)nums.size();
9
        vector<int> res(n);
10
        int i = 0, j = n - 1;
11

12
        for (int k = n - 1; k >= 0; --k) {
13
            // For integers, |x| > |y| is equivalent to x² > y²
14
            if (abs(nums[i]) > abs(nums[j])) {
15
                res[k] = nums[i] * nums[i];
16
                ++i;
17
            } else {
18
                res[k] = nums[j] * nums[j];
19
                --j;
20
            }
21
        }
22
        return res;
23
    }
24
};

1
function sortedSquares(nums) {
2
  const n = nums.length;
3
  const res = new Array(n);
4
  let i = 0;
5
  let j = n - 1;
6

7
  for (let k = n - 1; k >= 0; k--) {
8
    // For integers, |x| > |y| is equivalent to x² > y²
9
    if (Math.abs(nums[i]) > Math.abs(nums[j])) {
10
      res[k] = nums[i] * nums[i];
11
      i++;
12
    } else {
13
      res[k] = nums[j] * nums[j];
14
      j--;
15
    }
16
  }
17
  return res;
18
}

Complexity#

Common Pitfalls#

1. The result array must be filled from back to front. We can only determine the maximum value first; filling from front to back would reverse the order.
2. i <= j instead of i < j. For odd lengths, the middlemost element must also be written in.
3. Watch out for squaring overflow. In this problem |nums[i]| <= 10^4, the maximum square is 10^8, which int can hold; but if the problem were relaxed to 10^5 (square 10^10), C / C++ would have to switch to long long.
4. Don’t fool yourself with the square-then-sort approach. That requires O(n log n), wasting the information that “the array is sorted.”