Skip to main content

977. Squares of a Sorted Array

easyAsked at Duolingo

Return the squares of a sorted array in non-decreasing order — the kind of merge-from-ends two-pointer move that underpins Duolingo's leaderboard re-ranking, where positive and negative score deltas must be combined into a single sorted result efficiently.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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

Constraints

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

Examples

Example 1

Input
nums = [-4,-1,0,3,10]
Output
[0,1,9,16,100]

Explanation: After squaring: [16,1,0,9,100]; sorted: [0,1,9,16,100].

Example 2

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

Approaches

1. Brute force — square then sort

Square every element and then sort the resulting array.

Time
O(n log n)
Space
O(n)
function sortedSquares(nums) {
  return nums.map(x => x * x).sort((a, b) => a - b);
}

Tradeoff:

2. Optimal — two pointers from ends

Compare absolute values at both ends, fill result array from right to left with the larger square — single pass, O(n).

Time
O(n)
Space
O(n)
function sortedSquares(nums) {
  const n = nums.length;
  const result = new Array(n);
  let left = 0;
  let right = n - 1;
  let pos = n - 1;
  while (left <= right) {
    const lSq = nums[left] * nums[left];
    const rSq = nums[right] * nums[right];
    if (lSq > rSq) {
      result[pos--] = lSq;
      left++;
    } else {
      result[pos--] = rSq;
      right--;
    }
  }
  return result;
}

Tradeoff:

Duolingo-specific tips

Duolingo uses this as a two-pointer warmup: the naive sort is fine to mention, but interviewers expect you to spot that the input is already sorted — the largest squares always live at the extremes. The fill-from-right pattern comes up repeatedly in Duolingo's ranking and scoring pipelines. State the insight before writing code: 'The array is sorted, so the largest absolute value is at one of the two ends.'

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Squares of a Sorted Array and other Duolingo interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →