Find Intersection of Two Arrays

Given two integer arrays, X[] and Y[] of size m and n, write a program to find intersection of these two arrays. The intersection is a list of common elements present in both arrays. Suppose m > n, all array elements are distinct and intersection elements can be in any order. Note: This is an excellent problem to learn problem solving using various approaches.

Climbing Stairs Problem

There is a staircase of n steps, and you can climb either 1 or 2 steps at a time. Write a program to count and return the number of unique ways to climb the nth stair. The order of steps taken matters. Note: Climbing stairs is an excellent problem to learn dynamic programming approach and application of the Fibonacci series in problem-solving.

Find First and Last Position of Element in Sorted Array

Given an array of integers sorted in ascending order, write a program to find the first and last occurrence of a given element. Our goal should be to design an algorithm with O(log n) time complexity. Note: This is an excellent question to learn problem-solving using binary search. Here we need to apply binary search twice to solve this problem.

Remove nth node from end of list

The head pointer of a linked list is given, write a program to remove the Nth node from the end of the linked list and return its head. In other words, when the node is traversed from the end we have to delete the Nth node from there. Note: This is an excellent problem for beginners to learn problem solving using two pointers in a linked list.

Iterative Preorder, Inorder and Postorder Traversal using Stack

In recursive dfs traversals (preorder, inorder and postorder), output depends on the order in which we process the root node. Algorithm is simple and easy to visualize! The critical question is: How do we implement these traversals without using recursion? The answer is: We use stack to simulate a recursive dfs traversal into an iterative dfs traversal.

LRU Cache Implementation

The least recently used (LRU) cache is one of the popular caching strategies, which defines the policy to discard the least recently used items first from the cache and make room for new elements when the cache is full. It is used to organize items in order of their use, which allows identifying items that have not been used for a long time.

Least Frequently Used (LFU) Cache Implementation

The least frequently used (LFU) is a cache algorithm used to manage memory within a computer. In this method, the system keeps track of the number of times a block is referenced in memory, and when the cache is full, our system removes the item with the lowest reference frequency. LFU cache get and put operation works in O(1) average time complexity.

Product of array except self

Given an array X[] of n integers, write a program to find product[] array such that product[i] is equal to product of all array elements except X[i]. We need to solve this problem without using division operations. Note: This is an excellent product array puzzle to learn time complexity optimization using prefix array and a single loop.

Pair sum in an array

Given an array of n integers and a target number, write a program to find whether a pair sum exists in the array or not. In other words, we need to check for a pair of elements in the array that sum exactly to the target value. Assume that all elements are distinct. Note: This is an excellent problem to learn problem solving using two pointers and hash table.

Median of Two Sorted Arrays

There are two sorted arrays A and B of size n each, write a program to find the median of these two sorted arrays obtained after merging (new merged array will be an array of length 2n which is even). The median of a sorted array of size n is defined as the middle element when n is odd and the average of the middle two elements when n is even.

Insertion in Binary Search Tree (BST)

The root of the binary search tree and a key k is given. Write a program to insert key k into the binary search tree. Note: BST structure will change after the insertion. So we need to perform insertion in such a way that the BST property continues to hold. In this blog, we have discussed recursive and iterative implementations of insertion in BST.

Searching in Binary Search Tree (BST)

We start searching from root node and traverse a path downward in binary search tree. For each node in the path, compare target key k with the node key. If equal, search is successful. If k < node key, go to the left subtree. Similarly, if k > node key, go to the right subtree. In this blog, we have discussed recursive and iterative implementations of searching in BST.

Inplace Rotate Square Matrix by 90 Degrees

Given an n x n 2D matrix, write a program to rotate the matrix by 90 degrees in anticlockwise direction. We should rotate matrix 90 degrees without using extra space. In other words, we have to perform rotation by modifying 2D matrix directly. Note: This is an excellent problem to learn problem-solving using nested loops and transpose of a matrix.

Largest Subarray With 0 Sum

Given an array X[] of n integers, write a program to find the length of largest continuous subarray with zero sum. The subarray length starting from index i and ending at index j will be j - i + 1. So in other words, for all j > i, find max (j - i + 1) among all subarrays with zero sum.. Note: This is an excellent question to learn problem-solving using hash table.

Valid Mountain Array

Given an array X[] of n integers, return true if it is a valid mountain array. The array X[] is a mountain array if and only if n >= 3 and there exists some i with 0 < i < n - 1 such that: X[0] < X[1] <...X[i-1] < X[i] and X[i] > X[i+1] > ...> X[n - 1]. In other words, we call the array mountain array when the array is strictly increasing and then strictly decreasing.

Maximum Difference in an Array

Given an array A[] of n integers, find out the maximum difference between any two elements such that the larger element appears after the smaller element. In other words, we need to find max(A[j] - A[i]), where A[j] > A[i] and j > i. Note: This is an excellent problem to learn problem-solving using divide and conquer and a single loop.

N Repeated Element in Size 2N Array

In an array of size 2N, there are N + 1 unique elements, and exactly one of these elements is repeated n times. Write a program to return the N-repeated element in the given 2N size array. Note: This is an excellent problem to learn optimization using the mathematical approach. Sometimes mathematical insights into the problem can help us to get efficient solutions.

Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1. Write a program to compute how much water it can trap after raining. This is a famous interview problem to learn time and space complexity optimization using various approaches. Two pointers approach provides an efficient solution using O(n) time and O(1) space.

Maximum Subarray Sum (Kadane’s Algorithm)

Given an array of n elements, write a program to find the largest contiguous subarray sum. A subarray of array X[] is a contiguous segment from X[i] through X[j] where 0 <= i <= j <= n. Note: This is an excellent problem to learn problem solving using divide and conquer approach, dynamic programming and single loop (In place O(n) time solution).

Longest Substring Without Repeating Characters

Given a string S, write a program to find the length of longest substring without repeating characters. The substring is a continuous subpart of the string and we need to return the largest substring which has all unique characters. Note: This is an excellent problem to learn problem solving and time complexity optimization using sliding window approach.

Binary Search Algorithm

Binary search is an efficient algorithm to search a value in the sorted array using divide and conquer approach. It compares target value with value at mid-index and repeatedly reduces search interval by half. Searching continues until value is found or subarray size gets reduced to 0 (unsuccessful search). Time complexity of binary search is O(logn).

Search in a 2D Matrix

You have given row-wise and column-wise sorted 2d matrix and integer k, write a program to search k in 2d matrix, i.e. find whether k is present or not. Each row is sorted from left to right, and the first integer of each row is greater than the last integer of the previous row. Note: This is an excellent problem to learn problem solving binary search in a 2d matrix.

First Missing Positive

Given an array that includes both positive and negative numbers, write a program to find the first missing positive integer. This is one of the best problems for learning step-by-step time complexity optimization using various approaches. An in-place hashing solution uses the same input array to process values and generate output.

Bubble Sort, Selection Sort and Insertion Sort Algorithm

Learn design, implementation, analysis and comparison of bubble sort, selection sort and insertion sort. In data structures and algorithms, these are one of the fundamental sorting algorithms to learn problem-solving using incremental approach with the help of nested loops. All have the same worst case and average case time complexity.

Level Order Traversal (BFS Traversal) of Binary Tree

Level order traversal accesses nodes in level by level order. This is also called breadth first search or BFS traversal. Here we start processing from the root node, then process all nodes at the first level, then process all nodes at the second level, and so on. In other words, we explore all nodes at the current level before going to nodes at the next level.

Detect Loop in Linked List

Given the head of a linked list, write a program to find if linked list has a cycle or not. Return true if there is a cycle or loop in the linked list. Otherwise, return false. A linked list with cycle causes iteration to fail because the iteration will never reach the end. So, detecting a linked list loop is important before applying an iterative approach.

Validate Binary Search Tree (BST)

Given the root of a binary tree, write a program to check whether tree is a valid binary search tree (BST) or not. To check valid bst, we verify bst property at each node: All node values in the left subtree are less than node’s value, all node values in the right subtree are greater than node’s value, and both subtrees are also binary search trees.

Reverse a Linked List

A head pointer of a singly linked list is given, write a program to reverse linked list and return the head pointer of the reversed list. We need to reverse the list by changing the links between nodes. Note: This is an excellent question to learn problem-solving using both iteration (Three-pointers) and recursion (Decrease and conquer approach).

FizzBuzz Problem

FizzBuzz question: Given an integer n, write a program to return string representation of numbers from 1 to n. If number is divisible by 3, we store “Fizz”. If number is divisible by 5, we store “Buzz”. If number is divisible by both 3 and 5, we store “FizzBuzz”. Hint: This is an excellent puzzle to learn coding concepts like conditional statements, loops, etc.

Sort Characters by Frequency

Given a string S[], write a program to sort string S in decreasing order based on the frequency of characters. The frequency of a character is the number of times it appears in the string. If two characters have the same frequency, whichever occurs earliest in S, must come first. In other words, frequency based sorting must be stable.

Find Minimum in Rotated Sorted Array

A sorted and rotated array of size n is given, write a program to find minimum element in rotated sorted array. Rotation by k times means that the first k sorted elements of the array will move to the last k positions, and the last n - k sorted elements will move to the first n - k positions. Note: We don’t know how many times array is rotated in the given problem.

Merge Sort Algorithm

Merge sort is one of the fastest comparison based sorting algorithms, which works on the idea of divide and conquer approach. Worst and best case time complexity of merge sort is O(nlogn), and space complexity is O(n). This is also one of the best algorithms for sorting linked lists and learning design and analysis of recursive algorithms.

Quick Sort Algorithm

Quicksort algorithm is often the best choice for sorting because it works efficiently on average O(nlogn) time complexity. It is also one of the best algorithms to learn divide and conquer approach. In this blog, you will learn: 1) How quick sort works? 2) How to choose a good pivot? 3) Best, worst, and average-case analysis 4) Space complexity and properties of quicksort.

Valid Anagram (Check if Two Strings are Anagram or Not)

Given two strings, str1 and str2, of size m and n, write a program to check whether two strings are an anagram of each other or not. A string str1 is an anagram of str2 if characters of str1 can be rearranged to form str2. Note: This is an excellent string problem to learn problem-solving and optimization using direct address table.

Array Subset of Another Array

Given two unsorted arrays of size m and n, find whether one array is a subset of another array or not. An array Y[] will be a subset of another array X[] if each element of Y[] is present in X[]. Assume that there are no repeated elements in both arrays and n <= m. Note: This is an excellent problem to learn problem solving using various approaches.

Counting Sort Algorithm

Counting sort is a stable sorting algorithm that works in O(n) time and space complexity when input are integers in the range 0 to k and k = O(n). Instead of comparison, counting sort uses array indexing to determine position of elements. For each element x, it counts values less than x and places x directly into its correct position in the sorted array.

Queue using Stacks

Write a program to implement queue using stack. We should use stack operations like push, pop, top, size, and isEmpty for implementing queue operations like enqueue, dequeue, and front. In this blog, we have discussed two approaches for implementing queue using two stacks: 1) Dequeue O(1) and Enqueue O(n) 2) Enqueue O(1) and Dequeue O(1).

Wave Array Problem

Given an unsorted array of n integers, write a program to sort array into a wave array. There can be many possible waveforms, but we need to return any one of them. An array A[] is sorted in wave arrangement if A[0] >= A[1] <= A[2] >= A[3] <= A[4] >= ....and so on. Note: This is an excellent problem to learn problem-solving using a single loop.

Move Zeroes

Given an array X[] of n elements filled with several integers, some of them being zeroes, write a program to move all the zeros to the end. We need to preserve the relative order of non-zero elements and solve this problem in place using O(n) time complexity. Note: This is an excellent problem to learn problem solving using two pointers approach.

Max Consecutive Ones

A binary array X[] is given where elements are either 0 or 1. Write a program to find the maximum consecutive ones. The subarray with max continuous 1's can be present anywhere, starting from some index i and ending at some index j. This is an excellent problem to learn problem solving using a sliding window approach and single loop.

Majority Element

You are given an array X[] of n elements, write a program to find majority element in an array. A majority element is an element that appears more than n/2 times, so there is at most one such element. Assume that array is non-empty and majority element always exists in the array. Note: This is an excellent problem to learn various approaches.

Equilibrium Index of an Array

Write a program to find equilibrium index of an array. An array's equilibrium index is an index such that the sum of elements at lower indexes equals the sum of elements at higher indexes. Note: This is an excellent coding question to learn time and space complexity optimization using prefix array and a single loop using variables.

Minimum Coin Change Problem

Suppose we want to make a change for a given value K of cents, and we have an infinite supply of each of coin[ ] = [C1, C2, …, Cm] valued coins. Write a program to find the minimum number of coins required to make the change. Note: This is an excellent counting problem to learn problem solving using dynamic programming approach.

Remove Duplicates from Sorted Array

A sorted array is given, write a program to remove duplicates from sorted array. We need to remove repeated elements such that there is a single occurrence of each element and return the length of array containing unique elements. Note: This is an excellent problem to learn fast and slow pointers approach. We have discussed two O(n) time in place solutions.

Find Minimum and Maximum Element in Array

Given an array X[] of size n, write a program to find the maximum and minimum element in an array. Our algorithm should make the minimum number of comparisons. Note: This is an excellent question to learn problem-solving using a single loop and divide and conquer approach. In the efficient single loop solution, we increment the loop by two.

Minimum Number of Jumps to Reach End

An array of non-negative integers is given and the aim is to reach the last index in the minimum number of jumps. You are initially positioned at the first index of the array and each element in the array represents your maximum jump length at that position. Note: This is an excellent problem to learn problem solving using dynamic programming.

Sort an Array of 0s, 1s and 2s (Dutch National Flag Problem)

Given an array consisting of 0s, 1s, and 2s, write a program to sort this array of 0, 1, and 2 in ascending order. We need to sort the array in O(n) time complexity without using sorting algorithms or extra space. Note: This is a variation of the Dutch national flag problem and an excellent problem to learn problem solving using three pointers.

Find Maximum Element in a Bitonic Array

You are given an array of n integers that is first increasing and then decreasing. Write a program to find the maximum value in the array. Our goal should be to solve this problem using O(logn) time complexity. Note: This is an excellent problem to learn problem solving using binary search, where we modify binary search to get an efficient solution.

Spiral Traversal of Matrix

Given a 2-dimensional matrix, write a program to print matrix elements in spiral order. We can imagine spiral traversal as an ordered set of matrix segments with horizontal and vertical boundaries, where both boundaries are reduced by one at each step. Note: This is an excellent problem to learn problem-solving using iteration and recursion.

Container With Most Water

Given an array of n non-negative integers height[n], where each represents a point at coordinate (i, height[i]). n vertical lines are drawn such that endpoints of line i is at (i, height[i]) and (i, 0). Find two lines, which together with x-axis form a container, such that container contains the most water. This is an excellent problem to learn two pointers approach.

Kth Smallest Element

Given an array and a positive integer k, write a program to find the kth smallest element in the array. This is an excellent problem to learn problem-solving using the max and min heap data structure. The quick-select approach (divide and conquer) is also worth exploring because it helps to optimize time complexity to O(n) time average.

Leaders in an Array

Given an integer array X[] of size n, write a program to find all the leaders present in the array X[]. An array element is a leader if it is strictly greater than all elements to its right side. So the largest and last element of an array is a leader by default. Note: This is an excellent problem to learn problem-solving using a single loop and variables.

Kth Largest Element in BST

Given the root of a BST and an integer k, write a program to find the kth largest value among all the nodes' values in the binary search tree. Note: This is an excellent problem to learn problem solving using recursive and iterative inorder traversal and data structure augmentation (storing extra information inside BST nodes for solving a problem).

Minimum Absolute Difference in BST

Given the root of a binary search tree (BST), write a program to find the absolute minimum difference between the values of any two nodes in the tree. Here node values in the tree can be positive, negative, or zero. Note: This is an excellent problem to learn problem-solving using iterative and recursive inorder traversal of a binary tree.

Height (Maximum Depth) of a Binary Tree

Given the root node of a binary tree, write a program to find its height. The height or depth of a binary tree is equal to the count of nodes on the longest path from the root to leaf node, i.e., maximum number of nodes from the root to the most distant leaf. Note: This is an excellent problem to learn problem-solving using DFS and BFS traversal.

Max Continuous Series of 1s

You are given an array of 1s and 0s and you are given an integer k which signifies the number of flips allowed. Write a program to find the position of zeros which when flipped will produce a maximum continuous series of 1s. Note: This is an excellent problem to learn problem solving using sliding window technique in O(n) time and O(1) space.

Maximum Index

Given an array X[] of integers, find the maximum parity index. The parity index is the maximum index difference between two elements (X[i], X[j]) such that, j > i and X[j] > X[i]. In other words, we need to find maximum j - i such that j > i and X[j] > X[i]. Note: This is an excellent problem to learn problem solving using sorting and two pointers approaches

Intersection of Sorted Linked Lists

Write a program to find intersection of two sorted linked lists and return the head pointer of the new linked list. Here head pointers of both sorted linked lists are given as input and we shouldn’t do any changes in the structure to generate the output. Note: This is an excellent problem to learn problem-solving using recursion and two pointers in a linked list.

Middle of the Linked List

Given a singly linked list, write a program to find middle element of the linked list. We need to return the second middle node if the node count is even. Here the goal should be to use a single loop and O(1) extra space to find middle element. Note: This is an excellent problem to learn problem-solving using fast and slow pointers in the linked list.

Stack using Queue

Write a program to implement a stack using queues. We must use queue operations like enqueue, dequeue, front, size to implement stack operations like push, pop, and top. We have discussed three approaches: 1) Using two queues: O(n) pop and O(1) push 2) Using two queues: O(1) pop and O(n) push 3) Using one queue: O(1) pop and O(n) push.

Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth. The min depth of a binary tree is the number of nodes along the shortest path from root node down to the nearest leaf node. The path has to end on a leaf node. Note: An excellent problem to understand efficient problem solving using breadth-first search (BFS) when the solution node is nearest to the root node.

Check Equal Arrays

Given two integer arrays X[] and Y[], write a program to check if arrays are equal or not. Two arrays are equal if they have the same elements in any order. If there are repeated elements, then counts of repeated elements must also be the same for both arrays. Note: This is an excellent problem to learn problem solving using a hash table.

Longest Common Subsequence Problem

Given two strings X[] and Y[] of size m and n, design an algorithm to find the length of longest common subsequence (LCS). There can be many possible common subsequences of two strings, but we need to return the common subsequence of longest length. Note: This is an excellent problem to learn dynamic programming.

Find Next Greater Element

Given an array, find next greater element for every element in array (NGE). The next greatest for an element is the first largest element on the right side. Elements for which no next largest element exists, consider the next greater element as -1. Note: We have discussed two stack based solutions: 1) Traversing from left to right 2) Traversing from right to left.

Roman to Integer

Given a Roman number, write a program to convert Roman number to a corresponding integer value. What are Roman numbers? Roman numbers are the symbols used in a system of numerical notation based on the ancient Roman system. The symbols are I, V, X, L, C, D, and M, which represent integer values respectively for 1, 5, 10, 50, 100, 500, and 1,000.

Generating all K-combinations

Given two numbers n and K, write a program to find all possible combinations of K numbers from 1 to n. You may return answer in any order. Note: This is an excellent problem to learn problem-solving using the inclusion and exclusion principle of combinatorics and backtracking. We can use similar ideas to solve other problems.

Longest Consecutive Sequence

Given an array of n integers, find the length of the longest consecutive elements sequence. We need to find the length of the longest subsequence such that elements in the subsequence are consecutive integers. The consecutive numbers can be in any order. Note: This is an excellent problem to learn problem-solving using sorting and hash table.

Most Frequent Element in an Array

Given an array X[] of size n, write a program to find the most frequent element in the array, i.e. the element which occurs the most number of times. If multiple elements have maximum frequency, return the smallest (assume that at least one element is repeated). Note: This is an excellent problem to learn problem-solving using sorting and hash table.

Row With Max 1s

Given a boolean 2D array, where each row is sorted. Find the row with the maximum number of 1s. This is an excellent matrix problem that can be solved in linear time complexity. The best part is — we are using the sorted order property and nested loops to improve the solution over the binary search approach.

Subscribe to get weekly content on data structure and algorithms, machine learning, system design and oops.