How to study

To maximize your Leetcode study approach, begin with problems labeled as "Easy," concentrating on a specific topic—for example, with Trees. Do all variations on the topic, such as pre-order or in-order traversals for Trees, progress gradually from problems with higher acceptance rates and slowly move to Medium problems. Begin your problem-solving journey with a brute-force strategy, don’t try to begin with the most optimized solution. Once accomplished, shift your focus to optimization. This progression establishes a strong foundation before advancing to more challenging tasks.

When you hit a roadblock, set a timer, once you run out of time, check out editorials or forums for hints. Make sure you get the solution. Then, test your understanding by tackling a similar problem. It's like a quick workout for your coding skills – helps you flex those problem-solving muscles!

When you solve your problem, make sure you shoot me a tag on Linkedin and tell me about your solution ;).

How to track your progress

An essential aspect of your study routine is tracking your progress. To do this effectively, keep a record that includes the problem number, a brief problem description, your brute-force solution, your optimized solution, and the Big O notation for each problem. This spreadsheet serves as a valuable snapshot of your journey, allowing you to see how far you've come and providing a quick reference to reinforce your learning.

Here is a great blog post by Dan Kim, Leetcode Effectively: https://dandkim.com/leetcode-effectively/

Need motivation to be consistent?

Keep a log of your problems and by the end of the challenge, send it to me! You’ll be in for a surprise 🥸.

Cheers to your success!

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).

Problems:

(Don’t be discouraged that it is a medium problem. This is the “Hello World” of Two Pointers technique)

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

Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

Solution Animation

Optimal Solution: Use two pointers pattern with an auxiliary array. Time: O(N). Space: O(N

Given a 0-indexed integer array nums of length n and an integer target, return the number of pairs (i, j) where 0 <= i < j < n and nums[i] + nums[j] < target.

Optimal Solution: Sort the array and use two pointers to count pairs with a sum less than the target. Time: O(N log N). Space: O(N)

Given an array arr of n integers and an integer target, the task is to find a pair in arr such that it’s sum is closest to target.

Optimal Solution: Sort the array and use two pointers to find the maximum sum of distinct pairs less than k. Time: O(N log N). Space: O(1)

Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie.

Optimal Solution: Sort children and cookies; use two pointers to match greed to cookie size. Time: O(N log N + M log M). Space: O(1).

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Given a string s, return true if it is a palindrome, or false otherwise.

Optimal Solution: Use two pointers, one at the beginning and one at the end of the string. Move inwards, skipping non-alphanumeric characters and comparing characters. Time: O(N). Space: O(1).

You are given an integer array nums and an integer k. In one operation, you can choose two numbers from the array whose sum equals k and remove them from the array. Return the maximum number of operations you can perform on the array.

Optimal Solution: Sort the array. Use two pointers, one at the beginning and one at the end. If the sum equals k, increment the count and move both pointers. If the sum is less than k, move the left pointer. If the sum is greater than k, move the right pointer. Time: O(N log N). Space: O(1).

(this is an Easy problem when a Hash Map is used, aim to use the two-pointers technique)

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the i-th line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Optimal Solution: Use two pointers, one at the beginning and one at the end of the array. Calculate the area of the container formed by the lines at the pointers. Move the pointer pointing to the shorter line inwards, as moving the taller line will never increase the area. Keep track of the maximum area found. Time: O(N). Space: O(1).

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Optimal Solution: Sort the array. Then, iterate through the array and for each element, use two pointers (one starting from the next element and one from the end) to find pairs that sum up to the negative of the current element (using the two-sum approach). Avoid duplicate triplets. Time: O(N^2). Space: O(N) (to store the results).

STOP

Before continuing to the next section make sure you can answer the following questions:

  • When should you choose the two-pointer strategy?

  • What do all data structures that the problem has in common?

  • What is the time complexity of iterating with nested for loops?

  • What is the difference between iterating with two pointers and with a nested for loop?

Shoot me a LinkedIn post on what your answers, would love to know your progress ;).

Resources:

Intervals

What is the problem asking for?

An interval problem can usually be identified when the input is an array of pairs.

This type of problem heavily relies on knowing how to sort the pairs, usually with a custom sort.

For this type of problem, I recommend you draw a line and identify how the intervals interact with one another.

An introductory example of intervals is Merge intervals, which will be solved on day 56 (Don’t be discouraged that it is a medium problem, you’ll see how you can tackle this problem), goes as follows:

Given a set of time intervals in any order, merge all overlapping intervals into one.

Naive solution:

The naive solution would be to do a double for loop and compare by first, comparing the first interval with the rest of the intervals, if it overlaps with any other interval, remove it and merge it into the first interval. This solution takes O(N^2).

Custom Sort solution:

First sort the pairs, based on their start time (The first value of the pair).

Once sorted, push the first interval into a stack.

Iterate through the array and for each interval:

  • If the current interval does not overlap with the top of the stack, push the interval to the stack.

  • If the current interval does overlap with the top of the stack, update the stack top with the ending time of the current interval.

Once you are done iterating through all of the intervals, the stack will contain the merged intervals. This solution requires an O(N log N) time complexity and requires O(N) auxiliary memory.

Problems:

Given an array of intervals where intervals[i] = [start, end], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Optimal Solution: Sort the intervals based on their starting points. Iterate through the sorted intervals, merging any overlapping intervals into a single interval. Time: O(N log N) (due to sorting). Space: O(N) (in the worst case, to store the merged intervals).

Insert newInterval into sorted, non-overlapping intervals, merging if needed. Return the updated intervals.

Optimal Solution: Iterate, adding intervals before newInterval. Merge overlaps with newInterval. Add remaining intervals. Time: O(N). Space: O(N).

Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Optimal Solution: Sort by end times, greedily keep non-overlapping intervals. Time: O(N log N). Space: O(1).

Optimal Solution: Sort the intervals by start time. Then, iterate through the sorted intervals, checking if the current interval overlaps with the previous interval. If it does, return true. Time: O(N log N). Space: O(1).

Given a set of intervals, find the maximum number of mutually compatible (non-overlapping) intervals that can be selected.

Optimal Solution: Sort intervals by their finish times. Select the first interval. Then, iteratively select the next interval that starts after the finish time of the last selected interval. Time: O(N log N). Space: O(1).

STOP

Before continuing to the next section can you answer the following questions:

  • In which data structure would it be more convenient to store intervals?

  • In what cases is it convenient to create a custom sort?

  • Can intervals overlap in a valid list of non-overlapping intervals? (Trick question 😛)

  • How does the time complexity of merging intervals compare to sorting intervals?

You’ve got this! Look at all your progress so far! Which one has the most challenging problem for you?

Resources:

What is the problem asking for?

A binary search problem can be identified with the golden keywords: “maximum” or “minimum”.

This technique aims to reduce the time complexity of a linear search. Since a linear search iterates a data structure and evaluates each element, resulting in an O(N) time complexity.

So, binary search might sound a bit overwhelming, but it's not as bad as it seems, so bear with me.

A binary search cuts the time complexity of a search to O(log n). It does it disregarding half of the array based on the set conditions.

An introductory example, Binary Search, which will be solved in Day 16, goes as follows:

Given a sorted array and a target, write a function to search the target. If the target exists, then return its index. Otherwise, return -1.

Naive Solution:

Iterate through the sorted array and evaluate at each iteration if the iterator is pointing to the target. Return the iterator if it does. This solution is done in an O(N) time complexity.

Binary Search Solution:

To find the target element in the array using a binary search this is how the pattern looks like.

For a binary search, three key variables need to be declared: start, end, and middle.

start = 0

end = Array.size()-1

middle = start + (end - start) / 2

This formulation helps avoid potential integer overflow issues that might arise with the simpler expression middle = (start + end) / 2.

The start pointer can only move to the right, and the end pointer can only move to the left. At every step of this algorithm, evaluate whether the condition has been met and reevaluate the middle value. If it has not been met, we must evaluate where to go next. Whether we move Start or End will depend on the following conditions.

target < array[middle]. Then: end = middle - 1

target > array[middle]. Then: end = middle + 1

target == array[middle] return middle, you’ve found the answer!

Problems:

Given a sorted array nums and a target, write a function to search the target. If the target exists, then return its index. Otherwise, return -1.

Optimal Solution: Use binary search. Repeatedly divide the search interval in half. If the middle element is the target, return its index. If the target is less than the middle element, search the left half; otherwise, search the right half. Time: O(log N). Space: O(1).

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

Optimal Solution: Use binary search. If the target is found, return the index. If the target is not found, the left pointer will eventually point to the index where the target should be inserted. Time: O(log N). Space: O(1).

Given a non-negative integer x, compute and return the square root of x.

Since the return type is an integer, the decimal digits are truncated, and only the integer part of the result is returned.

Optimal Solution: Use binary search. Search for the integer ans such that ans * ans <= x but (ans + 1) * (ans + 1) > x. Time: O(log x). Space: O(1).

You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once.

Return the single element that appears only once.

Optimal Solution: Use binary search. The single element will cause a change in the pattern of pairs. Exploit this pattern to narrow the search range. Time: O(log N). Space: O(1).

Every house can be warmed, as long as the house is within the heater's warm radius range. 

Given the positions of houses and heaters on a horizontal line, return the minimum radius standard of heaters so that those heaters could cover all houses.

Optimal Solution: Sort houses and heaters. For each house, use binary search to find closest heaters and minimum radius. Time: O(N log M). Space: O(1).

(binary search is not the most optimal solution, but this problem is still great to practice this pattern! the next pattern will tech us how to solve this problem optimally!)

Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.

Binary Search Solution: Use a prefix sum array. For each possible start, binary search for the smallest valid end. Time: O(N log N). Space: O(N).

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

Resources:

STOP

Before continuing to the next section can you answer the following questions:

  • What is the key benefit of using binary search?

  • What is the time complexity of a binary search problem?

  • Can a binary search be applied to an unsorted array? Why or why not?

  • What is the main limitation of using binary search?

You see… it was not that bad ;).  👌👌

Sliding Window

What is the problem asking for?

A sliding window problem usually asks for subarrays that satisfy a condition; it may ask for a special subarray such as the shortest or longest that satisfies a certain condition, or the number of subarrays satisfying said condition.

An introductory example, Find maximum (or minimum) sum of a subarray of size k, solved on day 23, goes as follows:

Given an array of integers and a number k, find the maximum sum of a subarray of size k.

Naive solution:

The naive solution to this problem would be to generate all the subarrays of size k with a nested loop and keep track of the global and local minimum. This naive solution would have a time complexity of O(N^2).

Sliding Window Solution.

The sliding window technique is used when a specific operation needs to be done to just a “window” of the array. The idea is to reduce a nested loop to a single loop and do the operations to the window as it progresses and not calculate all of the subarrays of size k. This solution has a time complexity of O(N) and an auxiliary space of O(1).

First, calculate the sum of the first window by adding the first k elements.

Keep track of the sum with a max_sum variable.

To calculate the next window, subtract the first element of the array and add the arr[k+1] to the sum, updating the max_sum variable.

Iterate through the rest of the array, repeating the same steps.

When finishing all iterations of the array, return max_sum, which will have the maximum sum of a k-length subarray.

Problems:

Given an array of integers and a number k, find the maximum sum of a subarray of size k.

Optimal Solution: Apply the sliding window technique. Calculate the sum of the first k elements. Then slide the window, adding the new element and subtracting the oldest element to update the sum. Track the maximum (or minimum) encountered. Time: O(N). Space: O(1).

A string is good if there are no repeated characters.

Given a string s​​​​​, return the number of good substrings of length three in s​​​​​​.

Optimal Solution: Iterate through the string, checking each substring of length 3 for distinct characters directly within the loop. Time: O(N). Space: O(1).

Given a binary array nums and an integer k, return the maximum number of consecutive 1's in the array if you can flip at most k 0's.

Optimal Solution: Use the sliding window technique. Maintain a window with at most k zeros. Expand the window (right pointer) until you have more than k zeros. Then shrink the window (left pointer) until you have at most k zeros again. Keep track of the maximum window size found. Time: O(N). Space: O(1).

You are given a string blocks of length n where each character is either 'B' (black) or 'W' (white). You are also given an integer k.

You are allowed to perform an operation where you can recolor a white block to black.

Return the minimum number of operations that are needed so that there is a contiguous subarray of size k with all black blocks.

Optimal Solution: Use a sliding window of size k; slide it through the blocks, updating the count of white blocks within the window, and track the minimum count. Time: O(N). Space: O(1).

Given a binary array nums, you should delete one element from it.

Return the size of the longest non-empty subarray containing only 1's in the resulting array. Return 0 if there is no such subarray.

Optimal Solution: Use the sliding window technique. Maintain a window with at most one zero. Expand the window until you have more than one zero. Then shrink the window until you have at most one zero again. The maximum window size found (minus 1, since we're deleting one element) is the answer. Time: O(N). Space: O(1).

(now try to solve it with a sliding window!)

Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.

Optimal Solution: Use the sliding window technique. Expand the window until the sum >= target, then shrink the window to minimize the length while maintaining that condition. Time: O(N). Space: O(1).

Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.

Optimal Solution: Use the sliding window technique with a hash set (or frequency counter) to track the elements in the current window. As the window slides, add the new element and remove the leaving element. If all elements in the window are distinct (the size of the hash set is equal to k), update the maximum sum. If a duplicate is found, shrink the window until the duplicate is removed. Time: O(N). Space: O(K).

Given a string s, return the maximum number of occurrences of any substring under the following rules:

  • The number of unique characters in the substring must be less than or equal to maxLetters.

  • The substring size must be between minSize and maxSize inclusive.

Optimal Solution: Generate only substrings of length minSize (shortest allowed). Check each for the unique character constraint. Count occurrences of valid substrings with a hash map. Return the maximum count. The shortest valid substrings will have the maximum possible frequency. Time: O(N), dominated by substring generation and counting. Space: O(N), for the hash map.

Resources:

STOP

Before continuing to the next section can you answer the following questions:

  • What are the key considerations when choosing the size of the sliding window in a given problem?

  • How do you identify a sliding window problem?

  • What is the time complexity of doing the sliding window technique?

Conclusion

Congratulations on making it this far in your interview preparation journey! Through this guide, you've not only tackled various problem-solving techniques but also delved into the fundamental building blocks of data structures, particularly linear ones. These foundational concepts lay the groundwork for more complex problem-solving in interviews.

As you move forward in your preparation, keep in mind that the problems explored here are just the beginning. Data structures like arrays, and linked lists, and techniques like sliding windows and binary search are the building blocks. They provide a solid foundation that you can leverage to understand and master more advanced data structures and algorithms.

Be sure to give me feedback on this guide and to follow me on Linkedin!

All the best,

Denisse