- Denisse's Newsletter
- Posts
- Day 2 Solution: Two Pointers
Hello, brave human being,
Welcome back!
Before you read this email, make sure you’ve tried the solution on your own.
Let’s remember the problem….
Problem 977. Squares of a Sorted Array
Given a sorted array, return an array of the squares of each number sorted.
For this problem, it was not as straightforward that we would be using the two-pointers. Since you got a hint that this was the pattern to use, were you able to solve it?
Let’s first think about the naive solution. Iterate over the array, square them and re-sort them, having a time complexity of O(N log N). Although there is a faster solution using the technique learned.
What is the time complexity of solving this problem with two-pointers pattern?Remember, the array is already sorted |
Two pointers but how?
Initialize two pointers:
L = 0
R = Array.size() - 1
The left pointer can only move to the right, and the right pointer can only move to the left.
In this case, we are going to use an auxiliary array to store our squared numbers.
At each step of the algorithm, we check which of the two pointers has a greater absolute value. The greatest value is then stored last in our auxiliary array.
Let’s dig in with an example…..
Solution:
Day 2 Solution
Now let’s add the problem to our LeetCode tracker….
| Leetcode # | Summary | Naive Solution | Optimization | Big O Notation |
|---|---|---|---|---|
| 977 | Given a sorted array, return an array of the squares of each number sorted. | Iterate through the array, square each element, and then sort the array. | Use two pointers pattern with an auxiliary array. At each step of the algorithm, we check which of the two pointers has a greater absolute value. The greatest value is then stored last in our auxiliary array. | Naive Solution: Memory: O(1) Time Complexity: O(N log N) Optimization: Memory: O(N) Time Complexity: O(N) |
Need motivation to be consistent?
Add this problem to your log and when the challenge is done send it to me! You’ll be in for a treat.
Cheers to day 2,
Denisse
Intern opportunities :
Reply