LeetCode Squares of a Sorted Array Explained - Java

Preparing For Your Coding Interviews? Use These Resources
————————————————————

Other Social Media
----------------------------------------------

Show Support
------------------------------------------------------------------------------

#coding #programming #softwareengineering

[ful]

For future viewers, the reason why some questions say "non-decreasing" instead of "increasing" is because there might be duplicates. In that case, if you have [3, 3, 3, 3], it's not increasing, not is it decreasing. So "non decreasing" includes "not just increasing, but also the duplicates right beside each other"

[jovanstankovic]

No need to multiply two numbers twice in the if(A[negative_pointer] * A[negative_pointer] < A[positive_pointer] * A[positive_pointer]) statement. You can simply check if (A[negative number] * (-1) < A[positive_number]). Same effect but little more efficient.

Good job on these and thank you. Keep on going!

[winterheat]

this is great. I just needed to get squares of sorted array 350 years ago and it is great I get a refresher today

[TheMrxMF]

If you wanna simplify some things you can do this in one pass and make the code a bit simpler by adding your elements in reverse order to the result array. It's basically just a replica of merging two sorted lists reversed at that point.

[mcskrishna]

If we ignore the negative sign, the array can be seen as elements in decreasing order from both ends. Then it is a matter of doing merge sort of squared elements from both ends. Build target int[] while you merge.The loop at line 6 can be avoided.

[theSeniorSDE]

This was the question asked to me in today's interview

[hyperion]

Following solution is way simple then what has been depicted in this video:
public class Solution2 {

public static void main(String a[]) {
Solution2 obj = new Solution2();
obj.test1();
}

private void test1() {
int[] nums = {-4, -1, 0, 3, 10};
nums = sortedSquares(nums);
System.out.println(" nums is "+Arrays.toString(nums));

}

public int[] sortedSquares(int[] nums) {
int start =0;
int end = nums.length-1;
int idx = end;
int[] ans = new int[nums.length];
while(start <= end) {
int val1 = nums[start]*nums[start];
int val2 = nums[end]*nums[end];
if (val1 > val2) {
ans[idx] = val1;
start++;
}else {
ans[idx] = val2;
end--;
}
idx--;
}
return ans;
}
}

[akashhuyaar]

we can just use two pointers one from the start and the other one from the end, we don't need to find the positive positive pointer separately.

[jatinpabari]

Easy with 2 pointer
int length = nums.length;
int[] ans = new int[length];
int curr = length - 1;

for (int l = 0, r = length - 1; l <= r;)
if (Math.abs(nums[l]) > Math.abs(nums[r]))
ans[curr--] = nums[l] * nums[l++];
else
ans[curr--] = nums[r] * nums[r--];

return ans;

[sachinrathi]

They don't say increasing because there can be duplicate elements. So non-decreasing would still be a valid statement but increasing will not be.

[viraj_singh]

could also use a queue to store the squares of negative nums and compare the peek of this queue with the positive squares and dequeue if peek is <= current positive square

[GChief]

This is a two pointer solution any:
The negatives are going to be positive regardless
Arrays.sort can work

I like what LeetCode shows

public int[] sortedSquares(int[] A) {
int N = A.length;
int[] answer = new int[N];



//mutliply elements array
for(int i = 0; i < N; i++) {
answer[i] = A[i] * A[i];
}


//then sort
Arrays.sort(answer);
return answer;


}
}

[RubberFacee]

Your camera placement is blocking the code at 7:24

[jugsma]

They said non-decreasing because there maybe be repeated integers in the array.
[1, 2, 3, 4, 5, 6] and [1, 2, 3, 3, 4, 4] both are non-decreasing but not necessarily increasing.

[sonduong]

Can any one explain me why this way is efficient than the simple way that we square up the A array and then sort it again?

[yadav]

Swift Variant of your answer:
class Solution {
func sortedSquares(_ nums: [Int]) -> [Int] {
var start = 0
var last = nums.count - 1
var target: [Int] = Array(repeating: 0, count: nums.count)
var current = last
while (start <= last) {
let startValue = abs(nums[start])
let lastValue = abs(nums[last])
if startValue > lastValue {
target[current] = startValue * startValue
start += 1
} else {
target[current] = lastValue * lastValue
last -= 1
}
current -= 1
}
return target
}
}

[ankurbansal]

class Solution {
public int[] sortedSquares(int[] A) {
int[]arr = new int[A.length];
for(int i=0; i<A.length; i++){
arr[i] = A[i]*A[i];
}
Arrays.sort(arr);
return arr;
}
}

[andresalba]

how the hell is this an easy question lmao

[faisalrizwan]

Your solution will fail on all negative test case. [-5, -4, -3, -1]. Initially positive_pointer should be assigned to N. (int positive_pointer = N) to handle all negative cases.

[antonantochi]

O(N), S(1)
sorted(map(lambda x: x**2, A))