DSA-020 · Select largest square from sorted endpoints
Squares of a Sorted Array
Intermediate · Java 21 · Version 1 · editorial draft
Java reference and baseline verified on JDK 21: 6005 deterministic checks. Learner drafts are not executed.
Understand the problem
Return the squares of a nondecreasing int array in nondecreasing order, without modifying the input.
- nums is non-null and nondecreasing with 0–100,000 signed int values. Integer.MIN_VALUE is allowed. Sortedness is a precondition.
- Return a newly allocated long[] of the same length containing every squared input occurrence in nondecreasing order. Preserve nums. Empty input returns an empty long[].
- Widen before multiplication: the largest possible square is 4611686018427387904 (2^62), which fits in long. Do not use int multiplication or Math.abs(int) to handle the minimum int. Interactive fixtures use small exact integers; the Java harness verifies full-range boundaries.
Examples
Input:
[-7,-3,2,3,11]
Output:[4,9,9,49,121]The largest remaining magnitude is always at an endpoint.
Input:
[-2147483648,0,2147483647]
Output:[0,4611686014132420609,4611686018427387904]Both large squares are represented exactly by Java long.
Before you start
- Array indexing and inclusive pointer bounds
- Loop invariants and Java value versus reference semantics
Recognize the structure
Squaring breaks signed sorted order around zero, but the maximum magnitude of a sorted interval must be at an endpoint. Select the largest remaining square and fill the output backwards.
Try before revealing
Hint 1
Where can the greatest absolute value of a sorted interval occur?
Hint 2
Which output position should receive its square?
Hint 3
Compare endpoint long squares and fill from the last output position.
Derive the solution
Reveal the baseline, optimized reasoning, and Java code
Square then sort
Create long squares in source order and sort them. For [-3,-1,2], the buffer starts [9,1,4] and becomes [1,4,9]. This costs O(n log n) time and O(n) output plus sorting workspace. Comparing endpoint squares removes the comparison sort.
Improve the baseline
Find the extreme candidate
For any x between sorted endpoints a and b, |x|≤max(|a|,|b|). Therefore the largest remaining square belongs to the left or right endpoint.
Fill from the back
Compare the two long squares, write the larger at the last unfilled output position, and consume only its source endpoint.
Handle ties and empty ranges
On equal squares either endpoint is safe; the implementation chooses right. Exactly n iterations consume every occurrence. Empty input has no iterations or endpoint reads.
Why it is correct
Remaining multiset
Before each write, input[left..right] contains exactly the unconsumed source occurrences. Output positions after write contain their final largest squares in sorted order.
Safe placement
The larger endpoint square is the maximum of the remaining multiset. Writing it at the largest unfilled output index is therefore correct, and moving its endpoint removes precisely that occurrence.
Completion
Each iteration consumes one source and one output position. After n iterations every square has been placed; each earlier placement is at most the already-filled suffix. The final long[] is sorted and preserves multiplicity.
Complete Java reference and baseline
Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.
import java.util.Arrays;
public final class Solution {
public static long[] sortedSquares(int[] nums) {
long[] answer = new long[nums.length];
int left = 0, right = nums.length - 1;
for (int write = nums.length - 1; write >= 0; write--) {
long leftSquare = (long) nums[left] * nums[left];
long rightSquare = (long) nums[right] * nums[right];
if (leftSquare > rightSquare) { answer[write] = leftSquare; left++; }
else { answer[write] = rightSquare; right--; }
}
return answer;
}
public static long[] baseline(int[] nums) {
long[] answer = new long[nums.length];
for (int i = 0; i < nums.length; i++) answer[i] = (long) nums[i] * nums[i];
Arrays.sort(answer);
return answer;
}
}
Read the meaningful blocks
Cast before multiplying
(long) nums[left]*nums[left] widens the entire product. (long)(nums[left]*nums[left]) would preserve an already-overflowed int.
Avoid abs(int)
Math.abs(Integer.MIN_VALUE) is still negative because +2147483648 is outside int range. Comparing long squares avoids this trap.
Separate output from workspace
The answer needs n long cells even though pointer state is constant. Do not call the total space O(1).
Complexity
O(n) time, O(n) returned output storage, and O(1) other auxiliary workspace. The original array is read only.
The square-and-sort baseline costs O(n log n) time, O(n) output, and implementation-dependent sorting workspace. Java boundary tests use BigInteger squares as an independent arithmetic oracle.
Exact-state walkthroughs
Reveal normal and boundary traces
Fill the largest squares backwards
Input: [-7,-3,2,3,11] · Result: [4,9,9,49,121]
Step 1 of 7: Begin with an unfilled output.
No source occurrence has been consumed. Null display slots mean unfilled, not Java array contents.
- 0: -7
- 1: -3
- 2: 2
- 3: 3
- 4: 11
- 0: unfilled
- 1: unfilled
- 2: unfilled
- 3: unfilled
- 4: unfilled
| Variable | Value |
|---|---|
| values | [-7,-3,2,3,11] |
| left | 0 |
| right | 4 |
| answer | [null,null,null,null,null] |
See the affected Java block
1 import java.util.Arrays; 2 public final class Solution { 3 public static long[] sortedSquares(int[] nums) { 4 long[] answer = new long[nums.length]; 5 int left = 0, right = nums.length - 1; 6 for (int write = nums.length - 1; write >= 0; write--) { 7 long leftSquare = (long) nums[left] * nums[left]; 8 long rightSquare = (long) nums[right] * nums[right]; 9 if (leftSquare > rightSquare) { answer[write] = leftSquare; left++; } 10 else { answer[write] = rightSquare; right--; } 11 } 12 return answer; 13 } 14 public static long[] baseline(int[] nums) { 15 long[] answer = new long[nums.length]; 16 for (int i = 0; i < nums.length; i++) answer[i] = (long) nums[i] * nums[i]; 17 Arrays.sort(answer); 18 return answer; 19 } 20 } 21
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Begin with an unfilled output.
No source occurrence has been consumed. Null display slots mean unfilled, not Java array contents.
- values
[-7,-3,2,3,11]- left
0- right
4- answer
[null,null,null,null,null]
- Place the largest remaining square at the last unfilled position.
The filled suffix is final and sorted; each unconsumed square is at most the newly placed square.
- values
[-7,-3,2,3,11]- left
0- right
3- oldLeft
0- oldRight
4- leftSquare
49- rightSquare
121- write
4- answer
[null,null,null,null,121]
- Place the largest remaining square at the last unfilled position.
The filled suffix is final and sorted; each unconsumed square is at most the newly placed square.
- values
[-7,-3,2,3,11]- left
1- right
3- oldLeft
0- oldRight
3- leftSquare
49- rightSquare
9- write
3- answer
[null,null,null,49,121]
- Place the largest remaining square at the last unfilled position.
The filled suffix is final and sorted; each unconsumed square is at most the newly placed square.
- values
[-7,-3,2,3,11]- left
1- right
2- oldLeft
1- oldRight
3- leftSquare
9- rightSquare
9- write
2- answer
[null,null,9,49,121]
- Place the largest remaining square at the last unfilled position.
The filled suffix is final and sorted; each unconsumed square is at most the newly placed square.
- values
[-7,-3,2,3,11]- left
2- right
2- oldLeft
1- oldRight
2- leftSquare
9- rightSquare
4- write
1- answer
[null,9,9,49,121]
- Place the largest remaining square at the last unfilled position.
The filled suffix is final and sorted; each unconsumed square is at most the newly placed square.
- values
[-7,-3,2,3,11]- left
2- right
1- oldLeft
2- oldRight
2- leftSquare
4- rightSquare
4- write
0- answer
[4,9,9,49,121]
- Return the contract result.
All required values have been finalized under the declared contract.
- result
[4,9,9,49,121]
Equal endpoint magnitudes
Input: [-2,0,2] · Result: [0,4,4]
Step 1 of 5: Begin with an unfilled output.
No source occurrence has been consumed. Null display slots mean unfilled, not Java array contents.
- 0: -2
- 1: 0
- 2: 2
- 0: unfilled
- 1: unfilled
- 2: unfilled
| Variable | Value |
|---|---|
| values | [-2,0,2] |
| left | 0 |
| right | 2 |
| answer | [null,null,null] |
See the affected Java block
1 import java.util.Arrays; 2 public final class Solution { 3 public static long[] sortedSquares(int[] nums) { 4 long[] answer = new long[nums.length]; 5 int left = 0, right = nums.length - 1; 6 for (int write = nums.length - 1; write >= 0; write--) { 7 long leftSquare = (long) nums[left] * nums[left]; 8 long rightSquare = (long) nums[right] * nums[right]; 9 if (leftSquare > rightSquare) { answer[write] = leftSquare; left++; } 10 else { answer[write] = rightSquare; right--; } 11 } 12 return answer; 13 } 14 public static long[] baseline(int[] nums) { 15 long[] answer = new long[nums.length]; 16 for (int i = 0; i < nums.length; i++) answer[i] = (long) nums[i] * nums[i]; 17 Arrays.sort(answer); 18 return answer; 19 } 20 } 21
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Begin with an unfilled output.
No source occurrence has been consumed. Null display slots mean unfilled, not Java array contents.
- values
[-2,0,2]- left
0- right
2- answer
[null,null,null]
- Place the largest remaining square at the last unfilled position.
The filled suffix is final and sorted; each unconsumed square is at most the newly placed square.
- values
[-2,0,2]- left
0- right
1- oldLeft
0- oldRight
2- leftSquare
4- rightSquare
4- write
2- answer
[null,null,4]
- Place the largest remaining square at the last unfilled position.
The filled suffix is final and sorted; each unconsumed square is at most the newly placed square.
- values
[-2,0,2]- left
1- right
1- oldLeft
0- oldRight
1- leftSquare
4- rightSquare
0- write
1- answer
[null,4,4]
- Place the largest remaining square at the last unfilled position.
The filled suffix is final and sorted; each unconsumed square is at most the newly placed square.
- values
[-2,0,2]- left
1- right
0- oldLeft
1- oldRight
1- leftSquare
0- rightSquare
0- write
0- answer
[0,4,4]
- Return the contract result.
All required values have been finalized under the declared contract.
- result
[0,4,4]
Test the contract
Input:
[]
Output:[]No endpoint access.
Input:
[-5,-2,-1]
Output:[1,4,25]Negative side reverses under squaring.
Input:
[-2,0,2]
Output:[0,4,4]Equal magnitudes preserve both occurrences.
Input:
[-2147483648]
Output:[4611686018427387904]Minimum int square requires long.
Common mistakes and counterexamples
Square signed-sorted values and assume order remains
Counterexample: [-3,-1,2] becomes [9,1,4].
Merge by endpoint magnitude or sort the squares.
Multiply before widening
Counterexample: 50000*50000 exceeds Integer.MAX_VALUE.
Cast one operand to long first.
Take absolute value as int
Counterexample: abs(-2147483648) remains negative.
Use widened arithmetic or compare long squares.
Follow-ups
Return original indices with squares.
Write square/index records and define how equal squares are ordered. Choosing the right endpoint on ties does not guarantee a desired original-index tie order after backwards filling.
Merge two increasing square streams.
Locate the split at zero. Traverse negative numbers backwards and nonnegative numbers forwards, merging their increasing long-square streams in O(n) time.
Allow long input values.
Squaring an arbitrary long can exceed long range. Use BigInteger output or explicitly restrict input magnitude; widening from int to long solves only this problem’s declared domain.
Your Java attempt
Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.
Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.
No unsaved text changes · 90/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.