Category Archives: Array

Rotate Matrix By 90 Degree

Problem description: Given an N X N integer matrix, rotate it bye 90 degrees in place.In-place means minimal extra memory to be used, i.e. don’t make a new array to copy into). Rotate clockwise means top-row becomes right-column, right column becomes bottom-row etc. eg. Solution: The idea is to do a “four-way” swap variable, we Read More →

Combination Sum Problem

Problem: Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T. Each number in C may only be used once in the combination. Note: All numbers (including target) will be positive integers. Elements in a combination (a1, a2,…, ak) must Read More →

Product of All Other Array Numbers

Problem: Given an array of n integers where n>1, return an array of same size an input array where at every index of the output array should contain the product of all elements in the array except the element at the given index. Example: arr[] = {10, 4, 1, 6, 2} prod[] = {48,120,480,80,240} Solution: Read More →

Find the Missing Element in Arithmetic Progression

Problem: Find the missing number in an Arithmetic Progression. An Arithmetic Progression is defined as one in which there is a constant difference between the consecutive terms of a given series of numbers. You are provided with consecutive elements of an Arithmetic Progression. There is however one hitch: exactly one number from the original series Read More →

Find a Peak Element in Array

Question: A peak element in an integer array is defined as an element that is greater than its neighbors. Given an input array where num[i] ≠ num[i+1], find a peak element and return its index. The array may contain multiple peaks, in that case return the index to any one of the peaks is fine. Read More →

Sort an almost sorted array where only two elements are swapped

Problem: Given an almost sorted array where only two elements are swapped, how to sort the array efficiently? Expected time complexity is O(n) and only one swap operation to fix the array. Input: arr[] = {1, 5, 3} // 3 and 5 are swapped Output: arr[] = {1, 3, 5} The idea is to traverse Read More →

Count Pairs of Numbers with a Given Difference K

Given an unsorted array and a number n, find if there exists a pair of elements in the array whose difference is n. Return count of such pairs. Example k=4 and a[]={7,623,19,10,11,9,3,15} Output should be : 6 Pairs can be: 7,11 7,3 6,10 19,23 15,19 15,11 Solution: Time Complexity: O(NLogN) Space Complexity: O(1)

Find Buy/Sell Prices in Array of Stock Values to Maximize Profit

Problem: You have given a stock prices for next 10 days. Find out: max benefit in best time complexity in buy and sell 1 share ? Condition: Share must be sold any day after buying date. For ex: Share price in thousands 5 1 4 6 7 8 4 3 7 9 Max benefit 9 – 1 Read More →

Merging 2 Arrays without using Extra Space

Given two sorted arrays, A and B. Write a method merging the elements of B into A in sorted order. Assume A has a large enough buffer at the end to hold all of B’s elements. Solution: Suppose we want to merge two arrays a1 and a2. a1 has n elements and has space for Read More →

Largest Difference in an Array

You have an array of integers: int[] A = { 10, 3, 6, 8, 9, 4, 3 }; My goal is to find the largest difference between A[Q] and A[P] such that Q > P. If P = 1 and Q = 4 diff = A[Q] – A[P] diff = 9 – 3 diff = Read More →

Minimum Distance Between Array Elements

Given a non-negative integer array, Find the minimum distance between 2 distinct elements of A. Minimum Distance is defined as if P != Q then |(A[P] – A[Q])| Solution: Time Complexity: O(N)

Passing Car East or West Codility

A non-empty zero-indexed array A consisting of N integers is given. The consecutive elements of array A represent consecutive cars on a road. Array A contains only 0s and/or 1s: 0 represents a car traveling east, 1 represents a car traveling west. The goal is to count passing cars. We say that a pair of Read More →