Squares of a Sorted Array

📋

Problem

Imagine you have a list of elevations along a hiking trail, sorted from lowest to highest, and you want to analyze the squared elevation changes for some physics calculations.

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

1 ≤ nums.length ≤ 10^5-10^4 ≤ nums[i] ≤ 10^4nums is sorted in non-decreasing order

Edge cases: All positive numbers → output is squares in same orderAll negative numbers → output is squares in reverse orderSingle element array → output is square of that element

</>

IDE

def sortedSquares(nums: list[int]) -> list[int]:public int[] sortedSquares(int[] nums)vector<int> sortedSquares(vector<int>& nums)function sortedSquares(nums)

def sortedSquares(nums):
    # Write your solution here
    pass

class Solution {
    public int[] sortedSquares(int[] nums) {
        // Write your solution here
        return new int[0];
    }
}

#include <vector>
using namespace std;

vector<int> sortedSquares(vector<int>& nums) {
    // Write your solution here
    return {};
}

function sortedSquares(nums) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [16,1,0,9,100]Returning squares without sorting or merging, output not sorted.✅ Implement two-pointer merge from ends instead of sorting after squaring.

Wrong: [49,9,4,9,121]Sorting squares incorrectly or not sorting at all; output order wrong.✅ Use two-pointer approach comparing absolute values to merge squares in order.

Wrong: IndexError or crash on empty inputNo check for empty input before accessing array elements.✅ Return empty list immediately if input is empty.

Wrong: [25]Fails single element input due to pointer logic assuming multiple elements.✅ Handle single element arrays by returning square directly or adjust pointer logic.

Wrong: Timeout or slow response on large inputUsing sorting or nested loops causing O(n log n) or O(n^2) complexity.✅ Implement O(n) two-pointer approach to merge squares efficiently.

✓

Test Cases

Focus on handling empty and minimal inputs correctly.

Watch out for subtle bugs with negatives and zeros; test carefully.

Optimize your solution to linear time using two pointers.

t1_01basic

Input{"nums":[-4,-1,0,3,10]}

Expected[0,1,9,16,100]

⏱ Performance - must finish in 2000ms

Squares are [16,1,0,9,100], sorting them gives [0,1,9,16,100]

💡 Try using two pointers at the start and end of the array.

💡 Compare absolute values at both ends to decide which square to place next.

💡 Fill the result array from the end to the start with the larger square.

Why it failed: Output incorrect - likely forgot to sort squares or merge from ends. Fix by implementing two-pointer merge from opposite ends.

✓ Correctly merges squares from both ends into sorted order.

t1_02basic

Input{"nums":[-7,-3,2,3,11]}

Expected[4,9,9,49,121]

⏱ Performance - must finish in 2000ms

Squares are [49,9,4,9,121], sorted output is [4,9,9,49,121]

💡 Remember negative numbers squared become positive and can be larger than positives.

💡 Use two pointers to compare absolute values at both ends.

💡 Place the larger square at the current position from the end of the result array.

Why it failed: Incorrect output - likely sorting squares directly without two-pointer merge. Fix by merging squares from ends using two pointers.

✓ Correctly handles mixed negative and positive values with two-pointer approach.

t2_01edge

Input{"nums":[]}

Expected[]

⏱ Performance - must finish in 2000ms

Empty input returns empty output.

💡 Check how your code handles empty arrays.

💡 Ensure no index errors occur when input length is zero.

💡 Return empty list immediately if input is empty.

Why it failed: Fails on empty input - likely no check for empty array causing index errors. Fix by returning empty list if input is empty.

✓ Handles empty input gracefully.

t2_02edge

Input{"nums":[5]}

Expected[25]

⏱ Performance - must finish in 2000ms

Single element squared is the output.

💡 Test with single element arrays to verify base case.

💡 Ensure code does not assume multiple elements for two-pointer logic.

💡 Return square of the single element directly.

Why it failed: Fails single element case - likely two-pointer logic assumes at least two elements. Fix by handling single element case separately or correctly.

✓ Correctly handles single element input.

t2_03edge

Input{"nums":[0,0,0]}

Expected[0,0,0]

⏱ Performance - must finish in 2000ms

Zeros squared remain zeros, output same length with zeros.

💡 Zeros squared remain zero; check if code handles zeros correctly.

💡 Two-pointer approach should handle equal values properly.

💡 Ensure no off-by-one errors when all elements are identical zeros.

Why it failed: Fails all zero input - likely off-by-one or incorrect pointer movement. Fix by carefully updating pointers when values are equal.

✓ Correctly handles all zero input.

t3_01corner

Input{"nums":[-3,-2,-1]}

Expected[1,4,9]

⏱ Performance - must finish in 2000ms

All negative numbers squared produce sorted output in reverse order of input.

💡 Negative numbers squared become positive and largest squares come from largest absolute values.

💡 Two-pointer approach must compare absolute values, not just values.

💡 Fill result from end using larger absolute value square.

Why it failed: Fails all negative input - likely compares values directly instead of absolute values. Fix by comparing abs(nums[left]) and abs(nums[right]). This is the all-negative edge case test.

✓ Correctly handles all negative inputs by comparing absolute values.

t3_02corner

Input{"nums":[-1,0,1]}

Expected[0,1,1]

⏱ Performance - must finish in 2000ms

Mixed negative, zero, and positive values squared and sorted.

💡 Zero squared is zero and should be placed correctly.

💡 Two-pointer approach must handle zero correctly between negatives and positives.

💡 Compare absolute values and place squares accordingly.

Why it failed: Fails mixed zero input - likely pointer update logic incorrect when values equal zero. Fix by correctly moving pointers when abs values equal zero. This is the zero handling corner case.

✓ Correctly handles zero in mixed input.

t3_03corner

Input{"nums":[-5,-3,-2,0,1,4]}

Expected[0,1,4,9,16,25]

⏱ Performance - must finish in 2000ms

Mixed negatives and positives with zero, squares sorted correctly.

💡 Check that two-pointer approach merges squares correctly from both ends.

💡 Avoid greedy mistake of just squaring and sorting without merge.

💡 Use two pointers and fill result from end to start.

Why it failed: Fails mixed input with zero - likely greedy approach sorting squares directly instead of merging. Fix by implementing two-pointer merge from ends. This is the greedy trap test.

✓ Correctly merges squares from both ends for mixed input.

t4_01performance

Input{"nums":[-10000,-99980,-99960,-99940,-99920,-99900,-99880,-99860,-99840,-99820,-99800,-99780,-99760,-99740,-99720,-99700,-99680,-99660,-99640,-99620,-99600,-99580,-99560,-99540,-99520,-99500,-99480,-99460,-99440,-99420,-99400,-99380,-99360,-99340,-99320,-99300,-99280,-99260,-99240,-99220,-99200,-99180,-99160,-99140,-99120,-99100,-99080,-99060,-99040,-99020,-99000,-98980,-98960,-98940,-98920,-98900,-98880,-98860,-98840,-98820,-98800,-98780,-98760,-98740,-98720,-98700,-98680,-98660,-98640,-98620,-98600,-98580,-98560,-98540,-98520,-98500,-98480,-98460,-98440,-98420,-98400,-98380,-98360,-98340,-98320,-98300,-98280,-98260,-98240,-98220,-98200,-98180,-98160,-98140,-98120,-98100,-98080,-98060,-98040,-98020]}

Expectednull

⏱ Performance - must finish in 2000ms

Large input n=100, O(n) two-pointer solution must complete within 2 seconds.

💡 Use two pointers from opposite ends to achieve O(n) time.

💡 Avoid sorting after squaring to prevent O(n log n) time.

💡 Fill output array from end to start using larger squares first.

Why it failed: TLE due to O(n log n) sorting or O(n^2) approach. Fix by implementing O(n) two-pointer merge approach.

✓ Efficient O(n) two-pointer solution confirmed.

Practice

1. You are given an integer array and a target integer. The task is to find three integers in the array whose sum is closest to the target. Which approach guarantees an optimal solution with O(n²) time complexity?

easy

A. Sort the array and use a fixed pointer with two pointers scanning from both ends.

B. Use a brute force triple nested loop to check all triplets.

C. Apply dynamic programming to store sums of pairs and find closest triplet sum.

D. Use a greedy approach by picking the closest element to target and then two others.

Solution

1. Step 1: Understand problem constraints

   The problem requires finding three numbers whose sum is closest to a target, which suggests checking combinations efficiently.

2. Step 2: Identify approach with O(n²) complexity

   Sorting the array allows fixing one element and using two pointers to find pairs that sum closest to the remaining target, achieving O(n²) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting + two pointers is classic for 3Sum Closest [OK]

Hint: Sorting + two pointers reduces complexity to O(n²) [OK]

Common Mistakes:

• Thinking brute force is optimal
• Confusing DP with this problem
• Assuming greedy works for closest sum

2. You are given an array of integers and need to reorder it so that all even numbers appear before all odd numbers. Which algorithmic approach guarantees an optimal in-place solution with O(n) time and O(1) space complexity?

easy

A. Using a two-pointer technique that partitions the array in a single pass by swapping elements

B. Using dynamic programming to track even and odd counts and reorder accordingly

C. Sorting the array using a comparison-based sort and then grouping evens and odds

D. Using a brute force approach by creating two separate arrays for evens and odds and concatenating them

Solution

1. Step 1: Understand the problem constraints

   The problem requires reordering the array so that evens come before odds, ideally in-place and efficiently.

2. Step 2: Identify the optimal approach

   The two-pointer technique allows scanning the array once, swapping evens to the front, achieving O(n) time and O(1) space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two-pointer partitioning is classic for in-place parity partitioning [OK]

Hint: Two-pointer partitioning solves in-place parity grouping [OK]

Common Mistakes:

• Assuming sorting is needed for parity grouping
• Thinking DP applies to simple partitioning
• Believing extra arrays are optimal for in-place constraints

3. You are given a string and need to determine if it reads the same forwards and backwards, ignoring case and non-alphanumeric characters. Which approach guarantees an optimal O(n) time and O(n) space solution for this problem?

easy

A. Reverse the original string and compare it directly to the input string without any preprocessing.

B. Use dynamic programming to check all substrings for palindrome properties.

C. Use a greedy approach to skip characters that don't match and try to fix mismatches on the fly.

D. Preprocess the string by removing non-alphanumeric characters and converting to lowercase, then use two pointers from opposite ends to compare characters.

Solution

1. Step 1: Understand problem constraints

   The problem requires ignoring case and non-alphanumeric characters, so direct comparison or naive reversal won't work correctly.

2. Step 2: Identify approach that handles preprocessing and efficient comparison

   Preprocessing to clean the string and then using two pointers from opposite ends ensures O(n) time and space, and correctly handles all cases.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Preprocessing + two pointers is standard for palindrome checks ignoring punctuation [OK]

Hint: Preprocess then two pointers is optimal palindrome check [OK]

Common Mistakes:

• Trying to compare original string directly without cleaning
• Using DP which is overkill and slower
• Greedy skipping mismatches leads to incorrect results

4. Suppose the problem changes: you want to count pairs with absolute difference at most K, but now the array can contain duplicate elements and you want to count pairs where elements can be reused multiple times (i.e., pairs (i, j) with i ≤ j). Which modification to the binary search approach correctly handles this variant?

hard

A. Start binary search from i instead of i + 1 and count pairs where j ≥ i, adjusting count accordingly.

B. Use brute force nested loops to count all pairs with i ≤ j and difference ≤ K, as binary search cannot handle reuse.

C. Use two pointers with left starting at 0 and right starting at 0, moving right pointer forward and counting pairs including i = j.

D. Keep the same code but change bisect_right to bisect_left to include duplicates and allow i ≤ j pairs.

Solution

1. Step 1: Understand reuse and duplicates impact

   Allowing i ≤ j means pairs with the same element twice are valid; binary search must include current index.

2. Step 2: Modify binary search start index

   Starting bisect_right from i (not i+1) includes pairs where i == j; counting j ≥ i pairs correctly.

3. Step 3: Adjust counting logic

   Count pairs as j - i + 1 if including i == j, or carefully count pairs with j ≥ i.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Starting search at i and counting pairs with j ≥ i handles reuse correctly [OK]

Hint: Start binary search at i to include pairs with i == j [OK]

Common Mistakes:

• Using bisect_left instead of bisect_right incorrectly
• Ignoring pairs where i == j
• Assuming two pointers cannot handle reuse

5. Suppose you want to reverse a string but the input is a very large immutable string (e.g., Python str) instead of a mutable list. Which approach correctly handles this constraint efficiently?

hard

A. Convert the string to a list, reverse it using two pointers, then join back to a string.

B. Use a brute force approach creating a new reversed string by concatenation in a loop.

C. Use the recursive two-pointer approach on the string directly, swapping characters in-place.

D. Use a dynamic programming approach to build the reversed string from substrings.

Solution

1. Step 1: Understand immutability constraint

   Strings are immutable in Python, so in-place swaps are impossible directly on the string.

2. Step 2: Choose efficient workaround

   Converting to a list allows in-place two-pointer swaps, then joining back creates the reversed string efficiently in O(n) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Only Convert the string to a list, reverse it using two pointers, then join back to a string. respects immutability and is efficient [OK]

Hint: Immutable strings require conversion to mutable type for in-place reversal [OK]

Common Mistakes:

• Trying to swap characters in immutable string
• Using inefficient string concatenation in loop
• Misapplying DP to string reversal