Day 1 of 30 days of LeetCode patterns!

Welcome to the first day of becoming a LeetCode Pattern master,

For our first day, we are going to start with a pattern seen frequently in tech interviews.

Two-Pointers

What is the problem asking for?

To identify if a problem can be solved using two pointers you must look for similar types of requests: “count the number of pairs in an array”, or “return a pair of an array with a specific condition”.

An introductory example, Two Sum II, which will be solved in Day 1, goes as follows:

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

The given arrays are not typically sorted, and this two-pointer technique requires a sorted data structure, so bear this in mind.

If the problem asks for the original indices of the array, make sure you keep track of the original indices using something like an array of pairs, otherwise, sort it away!

Naive Solution:

Iterate through every pair of indices using two nested for loops that add up to the target. This results in a time complexity of O(N^2), with auxiliary memory of O(1).

Two Pointers 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. 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:

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

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

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

This technique allows us to solve the problem in a time complexity of O(N), with O(1) of auxiliary memory. Remember that if sorting is required, the time complexity increases to O(NlogN).

Problem:

Day 1:  167. Two Sum II - Input Array Is Sorted (Don’t be discouraged that it is a medium problem. This is the “Hello World” of Two Pointers technique)

Need motivation to be consistent?

Start your log with this problem and when the challenge is done send it to me! You’ll be in for a treat.

I’ll send the solution tomorrow with an editorial,

Stay tuned,

Denisse