What to do if you see a two pointers problem : Day 1 Solution

Try it before reading it!

Hello there,

Welcome back!

Editorial for the problem: 167. Two Sum II - Input Array Is Sorted

Given a sorted array of integers, find two numbers such that they add up to a specific target number.

Before you read this email, make sure you’ve tried the solution on your own.

What would the time complexity of the two-pointer solution be?

Login or Subscribe to participate in polls.

For this problem, we identified a crucial keyword: finding two numbers that add up to a specific target. This recognition led us to classify it as a two-pointer problem.

Now, let’s delve into the Two-Pointer solution.

Initialize a Left and Right pointer:

  • 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. The loop condition is while (L < R). When this condition is not true, it means the pointers have crossed each other or are pointing to the same element, indicating no more elements to check.

At every step of this algorithm, evaluate whether the condition has been met. Otherwise, move one of the two-pointers. Whether to move the left or the right pointer will depend on the following conditions:

  • If (arr[L] + arr[R]) < target, move the Left pointer one step to the right.

  • If (arr[L] + arr[R]) > target, move the Right pointer one step to the left.

  • If (arr[L] + arr[R]) == target, return the indices!

Let’s dig in with an example….. 

Day 1

Solution:

Day 1

Now let’s add the problem to our LeetCode tracker….

Leetcode Summary Table
Leetcode #SummaryNaive SolutionOptimizationBig O Notation
167Given a sorted array of integers, find two numbers such that they add up to a specific target number.Iterate through every pair of indices using two nested for loops that add up to the target.Two pointers strategy. Initialize the L=0, R=Array.size()-1. Evaluate conditions on two-pointers, choose which pointer to move or return L, R when the target is found.Naive Solution:
Memory: O(1)
Time Complexity: O(N^2)
Optimization:
Memory: O(1)
Time Complexity: O(N)

Cheers to day 1,

Denisse

LinkedIn Cold Outreach to recruiter tips

Julia Arpag: Julia Arpag is a titan in the recruitment space. She owns her recruiting firm and shares not only recruitment tips but also regular posts about real cases on how her clients are recruiting people.

Here are her 3 best tips to cold message a recruiter:

1. Personalize the crap out of your outreach.

2. Keep it insanely brief - pretend you're texting. 

3. Never resume dump.

Reply

or to participate.