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.

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 (the new merged array will be an array of length 2n). 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.

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.

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.

Count the number of possible triangles

Write a program to count the number of possible triangles that can be formed with three elements from a given unsorted array of positive integers. The three elements, representing the lengths of the sides of a triangle, must satisfy the triangle inequality: the sum of any two sides must be greater than the third side.

Detect Loop or Cycle 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.

Remove Duplicates from Sorted Array

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

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

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.

Find Triplets with Zero Sum

Given an array X[] of n distinct elements, write a program to find all the unique triplets in the array whose sum is equal to zero. For example, if triplets with zero sum in the array are (X[i], X[j], X[k]), then X[i] + X[j] + X[k] = 0. Hint: This is an excellent problem to learn problem-solving and optimization using hashing and two pointers approach.

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.

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.

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.

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.

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.

Middle of the Linked List

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

Subscribe to get well designed content on data structure and algorithms, machine learning, system design, object orientd programming and math.