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.

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.

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

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.

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.

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.

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.

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.

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.

Number of Buildings Facing Sun

Given an input array height[] which represents the heights of buildings, write a program to count the number of buildings facing the sunset. Assume that the heights of buildings are distinct. Insight: Here all buildings facing sunlight will be in increasing order. Note: This is an excellent problem to learn problem-solving using a single loop.

Swap Nodes in Pairs

Given the head pointer of a singly linked list, write a program to swap nodes in pairs and return the head of the modified linked list. If the number of nodes is odd, then we need to pairwise swap all nodes except the last node. Note: This is an excellent problem to learn problem solving using both iteration and recursion in a linked list.

Count Distinct Elements in Every Window

Given array X[] of n integers, write a program to return the count of distinct elements in every window of size k. Here k sized window is a continuous subarray of k elements, and output is an array with the count of unique elements in each window. Note: This is an excellent problem to learn problem-solving using the sliding window approach.

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.

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.

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