Arrays Flashcards
Rain Water Trapped
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
We keep two arrays.
Array 1 with list of Max Height on Left of an Index.
Array 2 with list of Max Height on Right of an Index.
For each index, water will fill upto
minOfHeight(Left,Right)
We subtract the height of building on this index from the value obtained
You are given an array of N integers, A1, A2, …. AN.
Return the maximum value of f(i, j) for all 1 ≤ i, j ≤ N. f(i, j) is defined as |A[i] - A[j]| + |i - j|, where |x| denotes absolute value of x.
We will make an assumption here that i will always be greater than j.
So |i-j| = i-j
|A[i] - A[j]| + i - j can be written in two possible ways, one of which will be our answer
A[i] - A[j] + i - j
(A[i]+i) - (A[j]+j) => F(i) - F(j) where F(n)= A[n]+n
OR
A[j] - A[i] + i - j
(A[j] - j) - (A[i]-i) => F(a) - F(b) where G(n) = A[n]-n
To Maximize above values we need to find values of n such that
Max(F(n)) - Min(F(n))
Max(G(n)) - Min(G(n))
ie
we need to find 4 variables: Max1,Min1, Max2, Min2
and just return the Max of (Max1-Min1, Max2-Min2)
Maximum Consecutive Gap
Given an unsorted integer array A of size N.
Find the maximum difference between the successive elements in its sorted form.
Try to solve it in linear time/space.
Eg 1 10 5 sorted will be 1 5 10
and max gap will be 5
We can’t sort entire array.
Lets start by finding the minimum possible value of our answer.
ie Min value of Maximum Gap will be the one in best case where every no is separated with the same gap
eg 1234 or 2468 10
Value of such a gap will be (MaxVal -MinVal)/noOFGaps
ie (4-1)/3 and (10-2)/4=> 1 & 2
now we create an array of these gaps storing the min and max value of each gap in every bucket
No of buckets will be Ceiling of (Entire Range Values)/gapSize
(max-min+1)/gapsize=> 4, 5
So we don’t need to calculate for values lying in our buckets.
we will fill these bucket array and subtract
the Max of a Left Bucket with min of Right Adjacent Bucket with values.
Carotenemia
You are given an Array of boxes A, where each box consists of oranges. You want to eat atleast B oranges. You start from the 0th index of the array, and keep eating oranges until you eat B oranges. If oranges from a box at ith index get depleted, you start eating from the (i+1)th box.
Determine index of the box where you finish eating B number of oranges. If you don’t eat B oranges even after eating from all the boxes, return -1.
We just keep reducing the value of B with array A values while traversing through it untill B is 0 or complete traversal.
Spiral Order Matrix II
Given an integer A, generate a square matrix filled with elements from 1 to A2 in spiral order.
Input: 4
Output:
[1, 2, 3, 4],
[12, 13, 14, 5],
[11, 16, 15, 6],
[10, 9, 8, 7]
We keep 4 variables Top,Left,Right and Bottom
For every iteration
We do 4 steps
Fill Top Row till Right Reached and update Top Value
Fill Right Column till Bottom Reached and update Right
Fill Bottom Row till Left Reached and Update Left
Fill Left Column till Top Reached and Update Left
Set Matrix Zeros
Update entire row and column of a 0 cell with 0.
Input :
[1, 0, 1],
[1, 1, 1],
[1, 0, 1]
Output 2:
[0, 0, 0],
[1, 0, 1],
[0, 0, 0]
Approach 1 is keep row and column values to update in two hashsets
And just traverse through entire 2d array check if its row or column lies in these stored values and update to 0.
Approach 2 when no extra space is Allowed
For each zero, we traverse through entire row and column of it and update the values to negative.
And in the end through entire matrix to replace negative values with 0’s
Approach 3 is we update the first row and first column with -1 which will mean that we have to update entire/row or column with 0
But for cell 0,0 we can keep 3 states
update row only
update column only
or update both based on the -ve value stored.
Implement the next permutation, which rearranges numbers into the numerically next greater permutation of numbers for a given array A of size N.
If such arrangement is not possible, it must be rearranged as the lowest possible order i.e., sorted in an ascending order.
Eg for input
123
132 will be OP
We traverse from right and keep comparing last two values
As soon as the Left Value is Smaller than the right one
we stop
1 2 3 6 5 4
Eg 3 & 6 here
So indexToReplace will be 3
We replace it with the just larger value on the right which is 4 so it becomes 124653 but still its not the next permutation We just reverse the rest array 124356
Eg 2:
123564>123654>123645
Reading Newspaper
You have a newspaper which has A lines to read.
You decided to start reading the 1st line from Monday. You are given a schedule, B, where B[i] = number of lines you can read on that day.
You are very strict in reading the newspaper and you will read as much as you can every day.
Determine and return, which day of the week you will read the last line of the newspaper.
We just keep reducing A till it is 0 while traversing through B
And return the day index at the end.
Sum of All Sub Matrices
Given a 2D Matrix A of dimensions N*N, we need to return sum of all possible submatrices. 1 2 3 4 So sum of all these values 1, 2, 3, 4 12 13 34 24 1234 Output: 40
We can’t just find out every submatix and then add.
Instead we try to find out the no of sub matrices Count every element x will fall into.
So for every element sum will be x*Count
Count can be easily determined using its row column values i,j
For Top Left => (i+1)(j+1)
For Bottom Right => (N-i)(N-j)
Total Count => (i+1)(j+1)(N-1)*(N-j)
for eg 12 34 we get count for each as 2*2*1*1=>4 4*1+4*1+4*3+4*4 40
Merge Intervals
Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.
Example 1:
Given intervals [1,3],[6,9] insert and merge [2,5] would result in [1,5],[6,9].
Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] would result in [1,2],[3,10],[12,16].
This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].
Make sure the returned intervals are also sorted.
Its not that hard.
We create methods to check whether intervals overlap
ie !(a.start>b.end || b.start>a.end);
one to merge two intervals, and one to check which interval is greater
We create an output array
and intitalize mergeInterval with newInterval values.
We traverse through initial array and keep merging the mergeinterval if it overlaps
If it doesn’t we add the mergedInterval and set mergedInterval to the new one.
In the end we compare mergedInterval and last one to check which is greater and add them in proper order.
Flip
You are given a binary string A(i.e. with characters 0 and 1) consisting of characters A1, A2, …, AN. In a single operation, you can choose two indices L and R such that 1 ≤ L ≤ R ≤ N and flip the characters AL, AL+1, …, AR. By flipping, we mean change character 0 to 1 and vice-versa.
Your aim is to perform ATMOST one operation such that in final string number of 1s is maximised.
If you don’t want to perform the operation, return an empty array. Else, return an array consisting of two elements denoting L and R. If there are multiple solutions, return the lexicographically smallest pair of L and R.
Initialize two variables L and R as -1
and one variable tempL
Also store values of diffCurr and diffMax
ie add +1 for every 0, and -1 for every 1
while traversing
if diffCurr becomes less than zero
set value of tempL to i+1
and reset diffCur to 0
if diffCur becomes greater than diffMax
set diffMax to diffCur
L to tempL
R to i
If L is still -1 return Blank
otherwise return values of L and R
Special Subsequences “AG”
You have given a string A having Uppercase English letters.
You have to find that how many times subsequence "AG" is there in the given string. Eg A = "ABCGAG" output 3 2 G after first A 1 G after second A
Just keep the value of count of ‘A’ while traversing through the string.
As soon as a G is found
add this value to total Sum.
First Missing Integer
Given an unsorted integer array A of size N. Find the first missing positive integer.
Note: Your algorithm should run in O(n) time and use constant space.
Inputs
[1, 2, 0]
[3, 4, -1, 1]
[-8, -7, -6]
Outputs
3
2
1
Max value of our answer can be the count of our array.
So let’s just create a new array with same size or use the initial one itself.
We will store i at A[i] while traversing through the array
Using same array we ignore if A[i]=i
else we put value of A[i] at A[A[i]]
and value of A[A[i]] at A[i]
and process i again.
In the end we traverse through the final array to check where A[i]= i
Merge Overlapping Intervals
Given a collection of intervals, merge all overlapping intervals.
We just sort the array first and then use same technique to merge as in similar question
Minimum swaps required to bring all elements less than or equal to k together
Given an array of integers A and an integer B, find and return the minimum number of swaps required to bring all the numbers less than or equal to B together.
Any 2 no’s can be swapped.
Input 1:
A = [1, 12, 10, 3, 14, 10, 5]
B = 8
Input 2:
A = [5, 17, 100, 11]
B = 20
Output 1: 2
Output 2: 1
Traverse through the array and find the no of items to be put together, ie count of all items less than B
Lets call this teamCount
traverse from 0 to teamCount
We need to find the range of an L to TeamCount
where the outliers are minimum
Eg: Input 1 for B=8
1,12,10,3,14,10,5
Team Count=3
from index 0 to 2 outliers are 2 from 1 to 3, we just check 0 and 3 and update outlier count its still 2 from 2 to 4 its 2 till end its 2 so our output is 2
