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"
I knew what they meant, but they could still just say ascending order. For example [1,2,2,3] *IS* sorted in ascending order (also non-decreasing, but that is obtuse).
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!
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.
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.
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 val2) { ans[idx] = val1; start++; }else { ans[idx] = val2; end--; } idx--; } return ans; } }
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]; }
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.
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 lastValue { target[current] = startValue * startValue start += 1 } else { target[current] = lastValue * lastValue last -= 1 } current -= 1 } return target } }
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.
Faisal Rizwan his solution wouldnt fail, if we take your case [-5, -4, -3, -1] as an example. The end of the first while loop will have positive_pointer = 4 and then negative_pointer will be 3. Since positive pointer is now equal to N, none of his positive pointer loops will run and only the negative_pointer >= 0 will. This will give him the correct answer
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"
rajon rondo Good observation! Never thought about that
@@NickWhite haha np, keep up the great videos man :)
I knew what they meant, but they could still just say ascending order. For example [1,2,2,3] *IS* sorted in ascending order (also non-decreasing, but that is obtuse).
Some might define that still as 'increasing' or 'ascending'. 'non decreasing' is just more confusing - [3,2,1,4] is also non decreasing
@@danieltannor6647 How is that non-decreasing? It goes from 3 to 2 to 1?
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!
Yesss
this is great. I just needed to get squares of sorted array 350 years ago and it is great I get a refresher today
This was the question asked to me in today's interview
in which company ?? and what time complexity did the ask you to solve this question?
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.
isnt it already a replica of merging two sets? could you please create a gist with your approach? :)
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.
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.
const squaresOfASortedArray = array => {
const result = []
let leftIdx = 0
let rightIdx = array.length - 1
let pointer = rightIdx
while (leftIdx Math.abs(largerValue)) {
result[pointer] = smallerValue * smallerValue
leftIdx++
} else {
result[pointer] = largerValue * largerValue
rightIdx--
}
pointer--
}
return result
}
@@jmdavaul thanks, this is brilliant.
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 val2) {
ans[idx] = val1;
start++;
}else {
ans[idx] = val2;
end--;
}
idx--;
}
return ans;
}
}
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.
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;
}
}
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.
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
Your camera placement is blocking the code at 7:24
yes
Awesome videos everytime 😁🔥🔥🔥❤️🔥🔥
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 lastValue {
target[current] = startValue * startValue
start += 1
} else {
target[current] = lastValue * lastValue
last -= 1
}
current -= 1
}
return target
}
}
Thanks Nic....Nice hair style.
class Solution {
public int[] sortedSquares(int[] A) {
int[]arr = new int[A.length];
for(int i=0; i
that's a naive solution man.
Are we allowed to use methods like sort()
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?
time and space complexity is better
if we sort the array again time is nlgn.
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.
Faisal Rizwan his solution wouldnt fail, if we take your case [-5, -4, -3, -1] as an example. The end of the first while loop will have positive_pointer = 4 and then negative_pointer will be 3. Since positive pointer is now equal to N, none of his positive pointer loops will run and only the negative_pointer >= 0 will. This will give him the correct answer
how the hell is this an easy question lmao
Thanks :)
what happened to ur hair bro LOL..........
O(N), S(1)
sorted(map(lambda x: x**2, A))
That's not O(n) that's O(nlogn)
the hair lol
int[] result = new int[nums.length];
int low = 0;
int high = nums.length-1;
int N = nums.length;
for(int i=0; i (nums[high] * nums[high])) {
result[N-i-1] = (nums[low] * nums[low]);
low++;
} else {
result[N-i-1] = (nums[high] * nums[high]);
high--;
}
}
return result;
It's very simple
class Solution {
public int[] sortedSquares(int[] nums) {
int idx = nums.length - 1;
int[] ans = new int[idx + 1];
int i = 0, j = idx;
while(i = Math.abs(nums[i])) {
ans[idx--] = nums[j] * nums[j];
j--;
} else {
ans[idx--] = nums[i] * nums[i];
i++;
}
}
return ans;
}
}