# Tagged: Arrays

## Find the first repeating character in a given string

Objec­tive: Given a string, write an algo­rithm to find the first repeat­ing char­ac­ter in it. Exam­ple: String input = “hori­zon tuto­ri­als” Out­put: ‘o’ String input = “algo­rithms” Out­put: No repeat­ing char­ac­ter found. Approach: Naive approach:…

## Find longest Snake sequence in a given matrix

Objec­tive: Given two dimen­sional matrix, write an algo­rithm to find out the snake sequence which has the max­i­mum length. There could be many snake sequence in the matrix, you need to return the one…

## 2D Matrix with Obstructions in it">Dynamic Programming — Count all paths in 2D Matrix with Obstructions in it

Objec­tive: Given two dimen­sional matrix, write an algo­rithm to count all pos­si­ble paths from top left cor­ner to bottom-right cor­ner. You are allowed to move only in two direc­tions, move right OR move down.…

## Dynamic Programming — Count all paths from top left to bottom right of a mXn matrix

Objec­tive: Given two dimen­sional matrix, write an algo­rithm to count all pos­si­ble paths from top left cor­ner to bottom-right cor­ner. You are allowed to move only in two direc­tions, move right OR move down. Example:…

## Reverse the given Array without using built in function

Objec­tive: Given a array, write an algo­rithm to reverse the array. Exam­ple: int a[] = {1, 2, 3, 4, 5} Out­put: {5, 4, 3, 2, 1} Approach: It’s obvi­ous that you can­not use any built-in…

## Print All Diagonals of a given matrix

Objec­tive: Given two dimen­sional matrix, write an algo­rithm to print all the diag­o­nals of matrix. Exam­ple: Approach: We will solve this prob­lem in two parts. first half of diag­o­nals and sec­ond half of diagonals.…

## Shortest Range in K-sorted Lists

Objec­tive: You have k lists of sorted inte­gers. Find the small­est range that includes at least one num­ber from each of the k lists. This is very nice and tricky solu­tion, This prob­lem was asked in…

## Find the Kth Smallest/Largest Element in an Array

Objec­tive: Given an array of inte­gers. find the Kth Smallest/largest ele­ment in the array. Exam­ple: int[] A = { 1, 2, 10, 20, 40, 32, 44, 51, 6 }; K=4. 4th small­est ele­ment in given…

## Find the Second Largest Element in an Array

Objec­tive: Given an array of inte­gers. find the sec­ond largest ele­ment in the array. Exam­ple: int[] A = { 1, 2, 10, 20, 40, 32, 44, 51, 6 }; Sec­ond largest Ele­ment : 44 Approach:…

## Merge K Sorted Arrays

Objec­tive: Given k sorted array, write an algo­rithm to merge Them into One sorted array. Exam­ple : int[][] A = new int[5][]; A[0] = new int[] { 1, 5, 8, 9 }; A[1] = new…

## Find a Number occurring odd number of times in a Given array

Objec­tive: Given a array of inte­gers, in which every ele­ments occurs even num­ber of times except one num­ber which occurs add num­ber of times. Find out that num­ber. Exam­ple:   int[] A = {…

## Rearrange the Array of Given Range N, such that A[i]=i

Algo­rithms — Rearrange the Array of Given Range N, such that A[i]=i. Objec­tive: Given a array of length N, in which ele­ments are in the range of 1 to N. All ele­ments may not…

## XOR Method">Find a Missing Number From a Sequence of Consecutive Numbers | XOR Method

Input:  Array, arrA[] with a miss­ing num­ber and Range Out­put : miss­ing num­ber Exam­ple: int A[] = { 1, 2, 7, 6, 3, 4 }; int range = 7; Out­put: MIss­ing No is :5 In…

## Binary Min — Max Heap

A binary heap is a heap data struc­ture cre­ated using a binary tree. binary tree has two rules — Binary Heap has to be com­plete binary tree at all lev­els except the last level. This…

## Magic Index — Find Index In Sorted Array Such That A[i] = i.

Objec­tive: Given a sorted array of dis­tinct inte­gers, Find the Magic index or Fixed point in the array. Magic Index or Fixed Point: Magic index or a Fixed point in an array is an index…

## Find Increasing Triplet Sub-sequence

Objec­tive: Given an inte­ger array A[1..n], find an instance of i,j,k where 0 < i < j < k <= n and A[i] < A[j] < A[k]. Exam­ple : int arrA[] = { 10, 9,…

## Construct a Special Triangle from a Given Array

Objec­tive: Given an array of inte­gers such that first level will print all the ele­ments in the array and from then at each level num­ber of ele­ments will be one less than the previous…

## Print All the Subsets of a Given Set (Power Set)

Objec­tive: Given a set of num­bers, print all the poss­si­ble sub­sets of it includ­ing empty set. Power Set: In math­e­mat­ics, Pow­er­Set of any given set S, PS(S) is set of all sub­sets of S including…

## Print All Combinations of subset of size K from Given Array

Objec­tive: Given an array of inte­gers of size N, print all the sub­sets of size k. (k<=N) Exam­ple: Gen­er­ate all sub­sets of a fixed size k of a given set [1,2,3…n]. e.g, if n=5…

## Track the Maximum Element in a Stack.

Objec­tive: In a Stack, keep track of max­i­mum value in it. It might be the top ele­ment in the stack but once it is poped out, the max­i­mum value should be from the rest…

## Print All Possible Valid Combinations Of Parenthesis of Given ‘N’

Objec­tive: — Given “n”, gen­er­ate all valid paren­the­sis strings of length “2n”. Exam­ple: Given n=2 Out­put: (()) ()() Approach:

## Counting Sort

Count­ing Sort is an sort­ing algo­rithm, which sorts the inte­gers( or Objects) given in a spe­cific range. Algo­rithm: Time Com­plex­ity O(n) Take two arrays, Count[] and Result[] and given array is input[]. Count[] will store the…

## Find The Missing Duplicate in a Given Array.

Objec­tive: — Given an Inte­ger array. Array con­tains dupli­cates of all the num­bers in array except one num­ber . Find that num­ber. Exam­ple : int [] A = { 2,1,3,5,5,3,2,1,6,7,7,8,8}; Out­put : Miss­ing duplicate…

## Implement Queue Using Stacks

Objec­tive: We know that Queue is FIFO (First-in-First-Out) and Stack is LIFO ( Last-in-First-Out). Here our objec­tive is to imple­ment queue using stacks. Approach: Take 2 Stacks, stack1 and stack2. stack1 will be used…

## Check if Array Contains All Elements Of Some Given Range

Objec­tive: Given an array of unsorted num­bers, check if it con­tains all ele­ments of some given range. Exam­ples: int[] arrA = { 11, 17, 13, 19, 15, 16, 12, 14 }; Range : 12–15 Output:…

## Check if Array is Consecutive Integers

Objec­tive: Given a array of unsorted num­bers, check if all the num­bers in the array are con­sec­u­tive num­bers. Exam­ples: int [] arrA = {21,24,22,26,23,25}; — True (All the inte­gers are con­sec­u­tive from 21 to…

## In an Array, find the Contiguous Subarray with Sum to a Given Value.

Objec­tive: Given an array and an inte­ger, find the Sub­ar­ray whose sum is equal to the given inte­ger. Exam­ples: int[] arrA = { 25, 12, 14, 22, 19, 15, 10, 23 }; Integer =…

## In an Array, find the Smallest Subarray with Sum Greater than the Given Value

Objec­tive: Given an array and an inte­ger, find the small­est sub­ar­ray whose sum is greater than the given inte­ger. Exam­ples: arrA[] = { 1, 5, 20, 70, 8} Inte­ger = 97 Out­put : Min…

## Rearrange Positive and Negative Elements at Alternate Positions in an Array In O(1) Extra Space

Objec­tive: Given an array arrA[] which has neg­a­tive and pos­i­tive ele­ments, rearrange the array in such a man­ner that pos­i­tive and neg­a­tive ele­ments occupy the alter­nate posi­tions and if there are extra pos­i­tive or…

## Find intersection between Two Sorted Arrays.

Objec­tive: Given two sorted arrays, Find inter­sec­tion point between them. Exam­ples: int[] a = { 1, 2, 3, 6, 8, 10 }; int[] b = { 4, 5, 6, 11, 15, 20 }; Output:…

## Find Kth Smallest or Largest element in an Array.

Objec­tive: Find Kth Small­est or Largest ele­ment in an Array Exam­ple: int[] arrA = { 2, 3, 11, 16, 27, 4, 15, 9, 8 }; Out­put: The 4th small­est ele­ment is : 8 Approach: Naive…

## Given an array arrA[], find the maximum j – i such that arr[j] > arr[i].

Objec­tive: Given an array arrA[], find the max­i­mum j – i such that arr[j] > arr[i]. Exam­ple: int[] arrA = { 12, 3, 1, 5, 6, 4, 10, 9, 8, 0 }; Out­put: Max(j-i)…

## Find All Elements in an Array which appears more than N/K times, N is Array Size and k is a Number.

Objec­tive: Given an array of size of N and num­ber k. Find all ele­ments in an Array which appears more than N/K times. Input: Array [] and num­ber k. Exam­ple: int[] arrA = { 2, 2,…

## Search an Element in a Rotated Sorted Array

Input: Rotated Sorted Array. What is Rotated Sorted Array. A sorted array is rotated around some pivot ele­ment. See the Exam­ple Below, array is rotated after 6. Approach:

## Sort an Given Array in the order defined by another array

Objec­tive: Given an array of inte­gers, write an algo­rithm to sort it accord­ing to the order defined by another array. Input: An Array of Inte­gers Exam­ple: Input Array : 2 6 9 1 4…

## Sort an Array such that the odd numbers appear first followed by the even numbers . The odd numbers in ascending order and the even numbers in descending order.

Objec­tive: Given an array of interg­ers, sort it such that the odd num­bers appear first fol­lowed by the even num­bers . The odd num­bers in ascend­ing order and the even num­bers in descend­ing order. Input:…

## Find the number of occurrences of a number in a given sorted array.

Objec­tive: Given a sorted(ascending order) arrays of inte­gers, find out the num­ber of occurences of a num­ber in that array Input: A sorted array arrA[] and a num­ber x. Out­put: num­ber of occur­rences of ‘x’ in…

## Find all common numbers in given three sorted arrays.

Objec­tive: Given three sorted(ascending order) arrays of inte­gers, find out all the com­mon ele­ments in them. Input: Three sorted arrays. Out­put: All the com­mon ele­ments. Exam­ples : Array A = {1,2,3,4,5,6,7,8,9,10}; Array B = {1,3,5,6,7,8,12};…

## Find the first repeated element in an array by its index

Objec­tive: Given an array of inte­gers, find out the first repeated ele­ment. First repeated ele­ment means the ele­ment occurs atleast twice and has small­est index. Input: An Array Out­put: The first repeated ele­ment Exam­ples : Array…

## Minimum number that cannot be formed by any subset of an array

Objec­tive: Given a sorted array of pos­i­tive inte­gers, find out the small­est inte­ger which can­not be rep­re­sented as the sum of any sub­set of the array Input: A Sorted Array Out­put: The small­est num­ber which…

## Count All Paths from Top left to bottom right in Two Dimensional Array including Diagonal Paths

Objec­tive: Count all the paths from left top cor­ner to right bot­tom cor­ner in two dimen­sional array. Input: Two Dimen­sional array Out­put: No of paths. Approach : 1. Recur­sive Recur­sive solu­tion to this prob­lem is…

## Print All Paths from Top left to bottom right in Two Dimensional Array

Objec­tive: Print all the paths from left top cor­ner to right bot­tom cor­ner in two dimen­sional array. Input: Two Dimen­sional array Out­put: Print all the paths. Note: At the End of the arti­cle you will…

## Rearrange Positive and Negative Numbers of Array On Each Side in O(nlogn)

Objec­tive: Rearrange Pos­i­tive and Neg­a­tive Num­bers of an Array so that one side you have pos­i­tive num­bers and other side with neg­a­tive Inte­gers with­out chang­ing their respec­tive order. Exam­ple : Input :  1 –2 3…

## Find The Longest Sequence Of Prefix Shared By All The Words In A String

Objec­tive: Write an algo­rithm to find The Longest Sequence Of Pre­fix Shared By All The Words In A String. This inter­est­ing prob­lem was asked in the Google inter­view for soft­ware engi­neer. This prob­lem is…

## Print All Elements of Two Dimensional Array in Spiral

Objec­tive: This ques­tion was asked in Ama­zon inter­view for the Soft­ware devel­op­ment Engi­neer posi­tion, Write an algo­rithm to print all the ele­ments of two dimen­sional array in spi­ral. Exam­ple : Input: Two dimen­sional array Output:…

## Find a pair of numbers from an array whose sum equals k

Objec­tive: Write an algo­rithm to find out whether in a given array there exists or not two num­bers whose sum is exactly equals to a given num­ber. This prob­lem has been asked in Amazon…

## Quick Sort Implementation

Objec­tive: Write an algo­rithm to sort an array in increas­ing or decreas­ing order using Quick Sort. Input:  An Array arrA[] Out­put: A sorted array. Approach: Choose any ele­ment from the array and call it as pivot element,…

## Find an Element in 2 dimensional sorted array

Objec­tive : Write an algo­rithm to find an Ele­ment in 2 dimen­sional array where rows and columns are sorted respec­tively. Input: A two dimen­sional sorted array, arrA[][].   Out­put : True or false based…

## Find a peak element in a Given Array

Objec­tive : In this arti­cle we will dis­cuss an algo­rithm to Find a peak ele­ment in a Given Array. We will see the recur­sion tech­niques to solve this prob­lem. Peak Ele­ment: peak ele­ment is…

## Find two Missing Numbers in a Sequence of Consecutive Numbers

Objec­tive : Write an algo­rithm to find two Miss­ing Num­bers in a Sequence of Con­sec­u­tive Num­bers Input:  Array, arrA[] with two miss­ing num­bers and Range Out­put : Two miss­ing num­bers Approach: Approach is very simple,…