Arrays

Question 1

Pick from both sides
Given integer array A of size N you can pick B elements from either left or right end of the array, and return the maximum sum.
If B=4, n=10, you can pick 4 from left, 4 from right, or 1 from left end and 3 from right end and so on.

Answer 1

Two pointer and sliding window concept.
Maintain 2 pointers l and r for number of elements on left end and right end resp. Intially l=B, r =0.
sum= sum of first b elements, res= sum
Now we keep decreasing the number of elements on left by one and increasing those on right by one. Instead of calculating sum again, we use sliding window concept. That is we subtract the element we are excluding from the sum and add the new element on the right which we are now including.
Rather than calculating the whole sum again.
sum-=A[l]
sum+=A[n-r]
Res is Max of two
Update values of l and r and repeat as long as l greater than or equal to 0

Question 2

Infinite Grid
On an infinite Grid, you can move in any one of the 8 directions. Given a sequence of points and the order in which you need to cover those points, find the minimum number of steps you can achieve it

Answer 2

For any two given points, we can have a rectangle formed by them of height h and breath b. Now to reach from one points to another in minimum steps, we move on the diagonal as much as we can, and cover the remaining part either horizontally or vertically.
No of diagonal steps=min(b,h)
No of remaining steps= max(b,h)- min(b,h)
Total= max(b,h)

This is for two given points. We need to repeat this for every two consecutive points in the array and add the total steps.

steps+= max( abs(a[i+1]-a[i]) , abs(b[i+1], b[i]))

Question 3

Minimum lights to activate
A corridor n units long has lights in each unit. The light at ith position is 0 if it is faulty, otherwise 1. All lights are of power B, and when placed at position x can light the corridor from x-b+1 to x+b-1. Initially all lights are off. Return the min number of lights to be turned on to light the white corridor.

Answer 3

At a given position we look for the rightmost bulb in the window which can cover this position. The adv of looking for the rightmost bulb is that it can cover more elements to its right as well. That is more coverage.

Initially i=0
While i less than n repeat the following
right= min(i+b-1,n-1)
Left= max(0,i-b+1)
found= false
Starting from right search for bulb non faulty. It will definitely cover the current position as it is in its window.
If found is false return -1( as no working bulb in the window to light the current position) Else, count++ and jump to right+ b and repeat.

Question 4

Maximum sum triplet

Given an array a of n integers, find the max sum of triplets ai +aj+ak such that i

Answer 4

For an element at a given position i in the array, we can get max sum including this element if we consider the greatest element on to its right, and the just smaller element on to its left. This will ensure that the sum is Max for the case we include this current element. We do this for every position and return the max of all such sums.
For this we maintain a right suffix array which stores the maximum element onto the right side of the given element.
We make use of set to find the just smaller element. We include all elements upto the current position including the current element. Search for current element in the set should return an iterator. The just smaller element will be at it-1.

Sum= *it-- + a[i]+ suffix[i]
res= max(res, sum)

Question 5

Given a non negative number represented as an array of digits, add 1 to the number. The digits are stored such that MSD is at the head of the list.The input can have 0s before MSD, the output cannot.

Answer 5

Find the starting index not including the zeros.
Initialise carry as 1 
Starting from the end till start index,
  If(a[i]+c >9) then a[i]=0, carry is 1
  Else a[i]+=c, carry is 0
  Push a[i] to new vector x

Do not forget to check if c=1 after processing element at start index. If so push 1 to the new vector.
Now reverse the vector and return

Question 6

Maximum absolute difference

Given an array of n integers, return max Val of f(i,j) for all 1<=i<=j<=n , f(i,j) =|a[i]-a[j]|+ |i-j|

Answer 6

Let us consider 4 cases
1 a[i]>a[j] and i>j 
    f(i,j) =(a[i]+i ) +(a[j]+j)
2. 
So on.  

Max1=max(max1, a[i]+i)
Min1=min(min1, a[i]+i)
Max2=max(max2, a[i]-i)
Min2=min(min2, a[i]-i)

The above 4 cases fall under one of the 2 categories
Res= max( max1-min1, max2-min2)

Question 7

Partitions
Given a 1D array, count the number of ways to split the array into 3 contiguous parts, such that the sum of elements in each part is same.

Answer 7

Firstly check if the sum of the entire array is a multiple of 3. Else return 0
Sum=sum/3
Maintain a prefix array which stores the indexes from left upto which the element sum to sum. There can be multiple indices as there can be zeros in the array( negative numbers?) So this way we are finding the partion on the left end which will add upto sum.
Similarly maintain a right suffix array which store index from right upto which elements add to sum. Again, there can be multiple.
For i in prefix and j in suffix, the region between prefix(i) to suffix(j) will anyway add upto sum. No need to check explicitly.
There should be atleast one element between prefix(i) and suffix(j) for third partition. So suffix(j) >= prefix(i)+2. For every such i and j we increment the count by one.

Question 8

Flip
Given a binary string of char 0 and 1, in a single opery you choose 2 indices l and r, and flip all elements between l and r so that the number of one’s in the final string is maximum.

Answer 8

Everytime we flip a 0 we get one extra 1, everytime we flip a 1 we lose a one. So we can associate +1 to 0 and -1 to 1. In such an array the solution to the above problem reduces to finding the maximum contiguous array, which can be found using Kadanes algo.

Question 9

Sort array with squares
Given a sorted array a with n elements both positive and negative, you need to create another array containing the squares of all elements in a and return it in non decreasing order.
That is if there is a 5 and -5 in the array, the sorted array of squares should contain 2 25s

Answer 9

We can make use of maps. For every element in the given vector, we find the square of the element and and use it as an index of the map. Everytime we get the same square either because of positive or negative elements, we increment the frequency of the square in the map. Then we iterate through the map and push the square into answer vector frq number of times.

Question 10

Max number from list

Given a list of non negative numbers, arrange them such that they form the largest number.

Answer 10

We make use of custom sort function. 
static bool comp( int x, int y)
 {  String X1= to_string(x)
   String y1= to_string(y)
   return (X1+y1> y1+X1}

We just sort the array using this custom sort function and they will be sorted in the order we want. Just traverse from left to right and convert each element to string and add to ans

What is the intuition behind custom sort func?

Question 11

Rotate image by 90 degrees in place

Answer 11

Rotation by 90 degrees can be done by first transposing the given matrix followed by reversing the rows

Question 12

Find permutation.
Given a positive integer n and a string s containing only letters i and d, find any permutation of first n positive numbers that satisfy the given string.

Answer 12

If i, pick the smallest number available, this would ensure that any number is greater than it, thus satisfying the condition i.
Similarly, if d, pick the greatest number available so that any number is lower than it.

Question 13

Merge overlapping intervals

Answer 13

First sort the intervals in the increasing order of their first values.
Now res=0, i=1
Repeat while i is less than n
If there is an overlap between a[res] and a[i], then merge. a[res].end will be the max of a[res].end and a[i].end. similarly start will be the minimum of the two.
Else if there is no overlap, then res++,
a[res]= a[i]
Answer will be all the intervals upto res.

Question 14

Noble integer
Given an integer array, find if an integer p exists such that the number of integers greater than p is equal to p. Return 1 if exists else -1

Answer 14

Cannot just order in decreasing order and check if a[i]=i, as there can be repeating digits.
Instead use a map to store the frequencies of each element.
Iterate through the map. This would be in increasing order. So the number of elements greater would be n-sum, where sum is sum of second values.
sum+=i.second
If(i.first==n-sum) return 1 else -1

Question 15

Next permutation
Implement next permutation which rearranges numbers in numerically next greater permutation of the numbers in the given array. If not possible then Inc order

Answer 15

Observe that every lexographic entry has a Inc part on its right. Find position starting from the right where a[i] <a></a>

Question 16

Wave array

Sort the given array into a wave and return it. If there are multiple answers, return lexographically smallest one.

Answer 16

After sorting the array swap the elements in pairs at index i and i +1

Question 17

Hotel bookings
A hotel manager has to process n adv bookings of rooms for the next season. His hotel has c rooms. Bookings contain an arrival date and a departure date. He wants to find out if there are enough rooms in the hotel to satisfy the demand.

Answer 17

Use custom sort function. Create pairs of of arrival dates and ‘a’ . Similarly create pairs of departure dates and ‘d’.
The custom sort function sorts then in the increasing order of either arrival or departure dates. If the dates are same, then departure is given priority.
For every ‘a’ yu increase the count by one. If count exceeds c, then not possible to satisfy demand. If ‘d ‘ then you decrease the count by one. Essentially count keeps track of the number of rooms currently occupied.

Question 18

Maximum distance

Given an array of integers, find the maximum j-i subject to a[i]<=a[j]

Answer 18

Store pairs of numbers and their indexes as pairs in an array cause when we sort the array, we will disturb the indexes.
Sort the pairs in the increasing order of the numbers, that is their first values
Now iterate through the pair of vectors which is now sorted. Keep track of min index. At every i we want to check if i- min index is maximum so far. That is the element at minimum index is the ith element in the question and the current element is the jth. Since the array is sorted, a[curr element ] will be any way greater than a[min index].
So our task is to keep track of min element and max ans. This is just O(n) unlike brute force which would have taken O(n^2).

Question 19

Maximum unsorted array
Given an A of n non negative numbers, find the minimum subarray such that if we sort that sub array, then the whole sub array should get sorted. Return the indices l and r of the sub array.

Answer 19

Simple!
Copy the given array into a temporary array and sort the temp array. Now starting from left check at which index there is a mismatch between the given array and the sorted array. This will the l
Similarly starting from right find the first time where there is mis match. That will give r.

Question 20

Perfect peak element
Given an array a , you need to check whether there exists an element which is strictly greater than all elements on the left and strictly smaller than all elements on the right.

Answer 20

Maintain prefix array and suffix array which keep track of maximum element on to left including itself and min element in to right respectively.
If a[i]= prefix (i) and suffix(i) and frequency of that element is one then return 1

Question 21

Pascal’s triangle

Given the number of rows, generate Pascal’s triangle upto n rows

Answer 21

To generate a[c] in row r we sum up a[c] and a[c-1] in row r-1 if i=0 or j= 0 then 1
J<= i

Question 22

Anti diagonal elements

Print anti diagonal elements of given 2d array

Answer 22

You have to print elements diagonally. So gap or i =0 to n-1
J=0 k=i
J<=j and k>=0
Vij = ajk
But this will give only upper half.
For lower half you have to do the same but from i= n to 2n-2. Look up

Question 23

Set matrix zeroes

Given a matrix of size mxn of zeros and ones, if an element is zero, set it’s entire row and column to zero.

Answer 23

Maintain two separate maps for rows and columns of size r and c.
Now traverse through the 2d array. Whenever you find a zero, mark the corresponding row and the corresponding colum in the map as 1 .
Now traverse again, if row(i ) is one or the column of (j) is one, then make that element zero in the array.
Simple!

Question 24

First missing number

Given an unsorted integer array containing both positive and negative elements, find the first missing positive number.

Answer 24

The smallest positive integer is 1. First check if one is present in the array or not. If not, return 1.
Notice that the ans lies in the range 1 to n+1. ( When first n positive int are given in the array) So make entries less than one and greater than n to 1. This will not change the answer. . With this all array entries are in the range 1 to n
For every ith element increase arr[i]-1 th element by n.
So if element at x is greater than n it implies there existed an array entry on value x+1
Therefore if we traversed the array, the first element at position i which is less than n, there was no element i+1 which could increase it. So i+1 is the first missing number.

Question 25

Kadanes algorithm

Answer 25

Int Maxx=arr(0)
For i from 0 to n
Sum+=arr(i)
If Maxx