Master Most Used

Problem Solving

Patterns

50
A
25 30
B C

40 10 30 60
D E F G

For Product Based Companies Interviews

How to effectively prepare for

Product Based Companies

Interviews?

Solving thousands of questions

Recognising frequently occurring

patterns and mapping new

questions to them

1
Two Pointers
Y Two pointers traverse the data structure together until a
specific condition is met.^
Y Handy for finding pairs in sorted arrays or linked lists, such
as comparing elements to each other in an arrayk
Y Can be of different types - both pointers starting from
same end, or one pointer at each end.

Example Problem

Given an array of integers nums and an integer target,

return indices of the two numbers such that they add
up to target.

The brute force approach would take two loops for

forming pairs and comparing their sum to target. 

This would take a time complexity of O(n^2) where n is

the length of the array.

2
We can use two pointers approach for an optimised solutio

 Sort the given array

0 Start two pointers. First pointer at the beginning of the

array and second one at end

/ Get current sum of pointer A and B, if current sum is

greater than target move pointer B back, else move pointer

A forward

Pointer 1 Pointer 2

1 2 3 5 6 9

1 + 9 > target sum, therefore let’s decrement Pointer 2

Pointer 1 Pointer 2

1 2 3 5 6 9

1 + 6 < target sum, therefore let’s increment Pointer 1

Pointer 1 Pointer 2

1 2 3 5 6 9

2 + 6 == target sum, we have found our pair!

3
The optimised solution using Two pointers would follow the
pseudocode

function PairSum(nums, target):

// Sort the array

sort(nums)

// Initialize the first pointer at the beginning of the

array

i = 0

// Initialize the second pointer at the end of the array

j = length of nums - 1

// Loop until the first pointer is less than the second

pointer

while i < j:

 // If we find a pair adding to the target

     if nums[i] + nums[j] == target:

     // Return the indices i and j as a pair

         return i, j

     // If the current sum is less than the target, move

towards higher values by incrementing i

     else if nums[i] + nums[j] < target:

         i++

     // If the current sum is more than the target, move

towards lower values by decrementing j

     else:

         j--

// If no pair is found, return 0 or an appropriate value

to indicate no pair was found

return 0

This version would only take O(nlogn) time complexity for

sorting the array.

4
Problems based on Two
Pointers:
% Remove Duplicates from Sorted Array -
LeetCod
% Squares of a Sorted Array - LeetCod
% 3Sum - LeetCod
% 3Sum Closest - LeetCod
% Sort Colors - LeetCod

% Backspace String Compare - LeetCode

5
Fast and Slow Pointers

 Also known as the Hare & Tortoise algorithm uses two

pointers which move through the data structure at
different speeds

Example Problem

Given a non-empty, singly linked list with head node

head we have to return the middle node. If there are
two middle nodes, we have to return the second
middle node.

A naive method would include two traversals of the

linked list, one to find the total length ‘n’ and one to
traverse till the ‘n/2th’ node and return it.

6
To solve this problem in a single traversal we can use the
Hare and Tortoise Approach 

There are two pointers used in this method, slow and fast

First with the fast pointer we move forward by two steps in

each iteratio
 With the slow pointer we move forward by only one step in
each iteration

When the fast pointer reaches the end of the linked list, the
slow pointer will have reached the middle of the linked list.

head

7 3 5 17 21 25 81

move slow pointer one step &

head slow fast fast pointer two steps

7 3 5 17 21 25 81

move slow pointer one step &

head slow fast fast pointer two steps

7 3 5 17 21 25 81

slow fast
head

7 3 5 17 21 25 81

slow fast
head

7 3 5 17 21 25 81

Middle Node

7
Pseudocode for Fast and
Slow Pointer Approach
slowPointer = head

fastPointer = head

while fastPointer is not null and fastPointer.next is not

null:

// Move slow pointer one step

slowPointer = slowPointer.next

    

// Move fast pointer two steps

fastPointer = fastPointer.next.next

// At this point, slowPointer is at the middle element

middleElement = slowPointer.data

8
Problems based on Slow and
Fast Pointer:
 Linked List Cycle - LeetCod
 Happy Number - LeetCod
 Palindrome Linked List - LeetCod
 Reorder List - LeetCod
 Circular Array Loop - LeetCode

9
 Sliding Window
 Used to perform a required operation on a specific window
size of a given array or linked lis
 Useful for problems dealing with subarrays or sublists

Example Problem

Given an array of positive numbers and a positive

number K, find the maximum sum of any contiguous
subarray of size K.

The naive solution will be to calculate the sum of all K

sized subarrays of the given array to find the subarray
with the highest sum.

This would result in a time complexity of O(N*K), where

N is the total number of elements in the given array

10
We can improve this approach by using the sliding window
technique to move the window over the array from index K to
the end of the array

 In each iteration, the window-sum is updated by removing

the element at the left side of the window (index i-K) and
adding the element at the right side of the window (index
i)

 Check if the window-sum is greater than the current max-

sum, and if so, update max-sum to keep track of the
maximum sum found so far.

k=3

1 2 6 2 4 1 window-sum=9

max-sum=9

1 2 6 2 4 1 window-sum=10

max-sum=10

1 2 6 2 4 1 window-sum=12

max-sum=12

1 2 6 2 4 1 window-sum=7

max-sum=12

11
Pseudocode for the Sliding
Window approach
function maxSumSubarrayOfSizeK(arr, K):

// Check for invalid input

if K > length of arr or K <= 0:

     return "Invalid input"

    

// Initialize variables

maxSum = 0

currentSum = 0

// Calculate the initial sum of the first window of size K

for i from 0 to K - 1:

     currentSum = currentSum + arr[i]

// Set the initial maxSum to the sum of the first window

maxSum = currentSum

// Slide the window and update maxSum until the end of the
array is reached

for i from K to length of arr - 1:

     // Remove the element at the left of the window and

add the element at the right

     currentSum = currentSum - arr[i - K] + arr[i]

     // Update maxSum if the currentSum is greater

     if currentSum > maxSum:

         maxSum = currentSum

// Return the maximum sum found

return maxSum

12
Problems based on Sliding

Window Approach:

- Maximum Average Subarray I - LeetCod

 Minimum Size Subarray Sum - LeetCod

 Longest Substring with At Most K Distinct

Characters - LeetCod

 Fruit Into Baskets - LeetCod

 Longest Substring with At Most Two

Distinct Characters - LeetCod

 Longest Substring Without Repeating

Characters - LeetCod

+ Max Consecutive Ones III - LeetCod

 Minimum Window Substring - LeetCod

$ Find All Anagrams in a String - LeetCode

13
 Merged Intervals
 This technique is used to deal with problems that require
you to find overlapping intervals.

Example Problem

Given a list of intervals, merge all the overlapping

intervals to produce a list that has only mutually
exclusive intervals.

In general there are 6 possible combinations for a pair of

intervals

Time

1) a b ‘a’ and ‘b’ not overlap

2) a ‘a’ and ‘b’ not overlap,

b ‘b’ ends after a

3) a ‘a’ completely overlaps ‘b’

b

4) a ‘a’ and ‘b’ overlap,

b ‘b’ ends after ‘b’

5) a ‘b’ completely overlaps ‘a’

b

6) a b ‘a’ and ‘b’ do not overlap

14
 The brute force approach would involve starting from the

first interval and comparing it with all other interval

 If current overlaps with any other interval, then remove the

other interval from the list and merge the other into the

first interva

 This leads to a time complexity of O(n^2) where n is the

number of intervals

Merge Overlapping Intervals

Input: (1, 4) (7, 9) (3, 6) (8, 10)

0 1 2 3 4 5 6 7 8 9 10

(1, 4) (7, 9)
(3, 6)

(8, 10)

Overlapping Intervals

Output:

Merged Intervals (1, 6) (7, 10)

15
The optimised version to solve the problem

 Sort the intervals according to the starting point of each

interval%

 Push the first interval into the stack%

 Iterate over each interval

 If the current interval does not overlap with the top of

the stack then, push the current interval into the stack%

& If the current interval does overlap with the top of the

stack then, update the stack top with the ending time

of the current interval%

 The stack now has the output merged intervals.

This version would have a time complexity of O(n*log(n)).

16
Pseudocode for the optimised

approach

function mergeIntervals(arr, n):

    // Test if the given set has at least one interval

    if n <= 0:

        return

    // Create an empty stack of intervals

    stack s

    // Sort the intervals in increasing order of start time

    sort arr 

    // Push the first interval to the stack

    s.push(arr[0])

    // Start from the next interval and merge if necessary

    for i from 1 to n-1:

        // Get the interval from the top of the stack

        top = s.top()

        // If the current interval is not overlapping with

the stack top, push it to the stack

        if top.end < arr[i].start:

            s.push(arr[i])

        // Otherwise, update the ending time of top if the

ending of the current interval is more

        else if top.end < arr[i].end:

            top.end = arr[i].end

            s.pop()

            s.push(top)

    return s

17
Problems based on Merge
Intervals Approach:

 Insert Interval - LeetCod

 Interval List Intersections - LeetCod
 Meeting Rooms - LeetCod
 Meeting Rooms II - LeetCod
! Car Pooling - LeetCod
 Employee Free Time - LeetCode

18
Depth First Search (DFS)

$ Recursive Algorithm used to search all the vertices of all a

graph or a tre

$ It starts from a chosen source node and explores as far as

possible along each branch before backtracking

Example Problem

Given a binary tree and a number S, find if the tree has a path
from root-to-leaf such that the sum of all the node values of
that path equals S.

This fits the DFS pattern as we are searching for a root-to-leaf

path

To solve this problem we can start from the root and at every
step, make two recursive calls one for the left and one for the
right child.

50

25 30

B C

40 10 30 60

D E F G

19
DFS Approach
9+ Start from the root of the tree and traverse the tree in a
depth-first manner!
+ If the current node is NOT a leaf node, do
 Subtract the value of the current node from the given
target sum to get updated sum value →  S = S -
node.valu&
 Make two recursive calls for left and right children of
the current node with updated sum value-
+ At every step, check if the current node is a leaf node and
if its value is equal to target sum S. If both conditions are
met, we have found the required root-to-leaf path,
therefore return true!
 If the current node is a leaf but its value is not equal to the
given number S, return false.

20
Pseudocode for DFS
Approach
function hasPath(root, sum):

    // If the current node is null (empty tree), return

false

    if root is null:

        return false

    // If the current node is a leaf node and its value

matches the sum we've found a path, so return true

    if root.value is equal to sum and root.left is null and

root.right is null:

        return true

    // Recursively call the function on the left and right

subtrees

    // Return true if any of the two recursive calls return

true,

    // indicating that a path with the desired sum was

found

    return hasPath(root.left, sum - root.value) OR

hasPath(root.right, sum - root.value)

21
Problems based on DFS
Approach:
$ Path Sum II - LeetCod!

 Binary Tree Paths - LeetCod!

 Sum Root to Leaf Numbers - LeetCod!

 Path Sum III - LeetCod!

 Diameter of Binary Tree - LeetCod!

 Binary Tree Maximum Path Sum - LeetCode

22
Breadth First Search (BFS)

' BFS is a graph traversal algorithm that systematically

explores all the nodes in a graph by visiting nodes in layers
or levels.$

' Starts from a chosen source node, visits all its neighbors,
then moves on to their neighbors, and so on, until all nodes
are visited or a specific condition is met.$

' Uses a queue data structure

Example Problem

Given a binary tree, populate an array to represent its level-

by-level traversal. You should populate the values of all nodes
of each level from left to right in separate sub-arrays.

1 Level 1

2 3 Level 2

4 5 6 9 Level 3

7 8 Level 4

⁘ LEVEL ORDER: 1, 2, 3, 4, 5, 6, 9, 7, 8

23
BFS Based Approach:

We basically have to visit the nodes of a higher level before

visiting nodes of a lower level

For this we use a queue data structure

* Start by pushing the root node to the queue

 Keep iterating until the queue is empty

 In each iteration, count the elements in the queue (let’s call

it levelSize). This is the number of nodes in the current

level

 Remove levelSize nodes from the queue and push their

value in an array to represent the current level

4 After removing each node from the queue, insert both of

its children into the queue.

If the queue is not empty, repeat from step 3 for the next level.

24
BFS Based Approach:

Level 1 3

Level 2 9 20

Level 3 15 7

We start by pushing root 3 into the queue.

Queue

Since the queue is not empty 3 is popped out and added to the

final traversal order. 

Its children 9 and 20 are pushed into the queue

Queue

9 20

Queue is not empty so 9 is popped out and added to final

traversal order

It has no children to push into the queue.

Queue

20

25
Now 20 is popped out and added to the final traversal order.

Its children 15 and 7 are pushed into queue

Queue

15 7

15 and 7 are popped out with the same process and we obtain
final level order traversal

This approach results in a time complexity of O(N) where N is

the number of nodes in the binary tree.

26
Problems based on BFS
Approach:
' Binary Tree Level Order Traversal II -
LeetCod
' Binary Tree Zigzag Level Order Traversal -
LeetCod
' Average of Levels in Binary Tree - LeetCod
' Maximum Level Sum of a Binary Tree -
LeetCod
-' Minimum Depth of Binary Tree - LeetCod
1' Maximum Depth of Binary Tree - LeetCod
"' Populating Next Right Pointers in Each
Node - LeetCod
' Binary Tree Right Side View - LeetCode
27
 Why

Bosscoder?
750+ Alumni placed at Top
Product-based companies.

More than 136% hike for every 


2 out of 3 working professional.

Average package of 24LPA.

Explore More