Squares of Sorted Array (LeetCode 977) | Full Solution with examples & animation | Study Algorithms

Usually we iterate through an array from the forward direction or the backward direction. Often we neglect the fact that we can also iterate the array from both the directions simultaneously. Watch this video to see how we can find the squares of a sorted array efficiently using two pointers head and tail. All along with animations and a dry-run of code in JAVA.

Chapters:
00:00 - Intro
00:51 - Problem statement and description
02:44 - Brute Force Solution
03:55 - Solving for efficiency using two pointers
06:59 - Dry-run of Code
09:36 - Final Thoughts

📚 Links to topics I talk about in the video:

📖 Reference Books:

🎥 My Recording Gear:

💻 Get Social 💻

#leetcode #programming #interview

[araneuskyuro]

Thank you so much bro!
Been racking my brain since the past 48 hours on this problem.
I appreciate the gradual and slow explanation with the brute force first.
Subscribed!

[NikhilKoshti-fs]

I have a shorter code in which I am comparing the squares instead of writing another loop. Started coding at 05:20 and arrived at the following code. Thanks for an explaination.
`
int tail = nums.length - 1;
int head = 0;
int idx = nums.length - 1; // to keep track of index of res array
int[] res = new int[nums.length];

while (tail >= head) {
if ((nums[head] * nums[head]) > (nums[tail] * nums[tail])) {
res[idx--] = (nums[head] * nums[head]); // assigning value and decrementing idx in a one line
head++;
} else {
res[idx--] = (nums[tail] * nums[tail]);
tail--;
}
}
return res;
`

[mustafasabir]

@9:20 Slight correction, The time complexity is O(2n) = O(n) because the array is traversed twice, once for squaring all the numbers and once for comparing for placement in new array.

Also if there is a requirement for something similar in API terms then there can be a solution where you do not modify the original input and just use a single array. Because at any time you are only comparing 2 squares you need not create a separate array of squares, you can store left pointer, right pointer, left square and right square in 4 variables and then do the iteration and store it in the new array directly.

class Solution:
def sortedSquares(self, A: List[int]) -> List[int]:
return_array = [0] * len(A)
write_pointer = len(A) - 1
left_read_pointer = 0
right_read_pointer = len(A) - 1
left_square = A[left_read_pointer] ** 2
right_square = A[right_read_pointer] ** 2
while write_pointer >= 0:
if left_square > right_square:
return_array[write_pointer] = left_square
left_read_pointer += 1
left_square = A[left_read_pointer] ** 2
else:
return_array[write_pointer] = right_square
right_read_pointer -= 1
right_square = A[right_read_pointer] ** 2
write_pointer -= 1
return return_array

[devbhattacharya]

One of the best explanations on youtube... :)...Thanks a lot sir

[omkarkhandalkar]

waiting for such more approaches
lots of love from Mumbai❣

[naveenaravindh]

It helps.. you deserve subscriptions..👍🏻

[TheHariPutraOfficially]

Bhaiyya you look like my cousin brother
..that's why I feel connected to you....thanksss

[vlogsaryan]

In the else loop in comment //increment tail pointer . I can't understand u do it by mistake or it's something else 😕

[KamranRasheed-osyw]

when you are getting the square of each integer in the array, could you also use the Math.pow method?

[kirankumargs]

We can ignore the traversal of input array to square the integers.


int n = nums.length;
int[] result = new int[n];
int head = 0;
int tail = n - 1;
for (int i = n - 1; i >= 0; i--) {
int headSquare = nums[head] * nums[head];
int tailSquare = nums[tail] * nums[tail];
if (headSquare > tailSquare) {
result[i] = headSquare;
head++;
} else {
result[i] = tailSquare;
tail--;
}
}
return result;

[shubhamagarwal]

Can it also be done without taking extra array to copy.

[la.flameCj]

can we solve this without using extra space ?