Arrays

Question 1

Reverse Array in groups

Answer 1

as questions sounds reverse array in groups with while loop
O(n) processing each element once

void reverse(int arr[], int n, int k) 
{ 
    for (int i = 0; i < n; i += k) 
    { 
        int left = i; 

        // to handle case when k is not multiple of n 
        int right = min(i + k - 1, n - 1); 

    // reverse the sub-array [left, right] 
    while (left < right) 
        swap(arr[left++], arr[right--]); 

}  }

Question 2

K’th smallest element

Answer 2

using heaps (TODO)

Question 3

Trapping Rain Water

Answer 3

1. use two arrays left_max and right_max precompute left and right max and value at element result += Math.min(left_max[].right_max) - arr[i] (because lower hight can only be filled - the height of the element)

Question 4

Pythagorean triplet

Answer 4

1.Sort the Array
2. find the square of two numbers using meet in the middle alg
o(n^2)

Question 5

Chocolate Distribution Problem

Answer 5

goal is to find the min diff among n packets

1. Sort the array
2. calculate the diff between i and i + k -1
3. update if less than the minimum and store the start and end index

O(nlogn) sorting

Question 6

Stock buy and sell

Answer 6

1. Store the local minima (while arr[i + 1] < arr[i] ++)
2. check if array last element (then not found after this)
3. save local minima
4. store local maxima
5. Count++

Question 7

Element with left side smaller and right side greater

Answer 7

1. calculate left max array
2. start with the end
3. if element is greater than left max and less than right min update

o(n)

Question 8

Convert array into Zig-Zag fashion

Answer 8

take a flag
if true check swap if next element greater than current
else
if flag is false swap if next element is smaller than current

Question 9

Last Index of 1

Answer 9

modified version of binary seach
check if the element is 1 and if element left to it is 0
else
if 1 search towards left of it 
else towards right of it

o(logn)

Question 10

Spirally traversing a matrix

Answer 10

maintain four index which serves as start and end indices of the row and columns
respectively increase/ decrease the rows and columns

Question 11

Largest Number formed from an Array

Answer 11

use a custom comparator which takes to two string
sort according to this comparator
this sort function sorts on the bassis of if XY > YX
use CompareTo in c# which returns -1 1

Question 12

SubArray with given sum

Answer 12

idea is to maintain a curr_sum which adds the number one by one
and check if this sum already exists in the hash map or not
if does return the index
else if the array is traversed then no sum found

cur_sum = cur_sum + arr[i]; 
            //check whether cur_sum - sum = 0, if 0 it means  
            //the sub array is starting from index 0- so stop  
            if (cur_sum - sum == 0) 
            { 
                start = 0; 
                end = i; 
                break; 
            } 
            //if hashMap already has the value, means we already   
            // have subarray with the sum - so stop  
            if (hashMap.ContainsKey(cur_sum - sum)) 
            { 
                start = hashMap[cur_sum - sum] + 1; 
                end = i; 
                break; 
            } 
            //if value is not present then add to hashmap  
            hashMap[cur_sum] = i;

Question 13

Count the triplets

Answer 13

Create a max_val element with max value int in the array

create an array freq and store the frequencies of each element

int[] freq = new int[max_val + 1];

there can be four cases for this

// Case 1: 0, 0, 0 
// Case 2: 0, x, x
// Case 3: x, x, 2x
// Case 4: x, y, x + y

//1
ans+= freq[0] + (freq[0] - 1 ) * (freq[0] - 2/)6

//2

for(int i = 0; i < n; i++){
ans+= freq[0] + (freq[i] - 1)* (freq[[i] - 2])/6
}

//
ans += freq[i] * (freq[i] - 1) /
2 * freq[2 * i];

//4

for (int i = 1; i <= max_val; i++) 
    { 
        for (int j = i + 1;  
                 i + j <= max_val; j++) 
            ans += freq[i] * freq[j] *  
                             freq[i + j]; 
    }

Question 14

Kadanes algo

Maximum subarray sum contiguous

Answer 14

int max_so_far = a[0];
int curr_max = a[0];

for (int i = 1; i < size; i++)
{
curr_max = max(a[i], curr_max+a[i]);
max_so_far = max(max_so_far, curr_max);
}

Question 15

Missing number in array

Answer 15

int x1 = a[0];
int x2 = 1;

        /* For xor of all the elements  
        in array */
        for (int i = 1; i < n; i++) 
            x1 = x1 ^ a[i]; 

        /* For xor of all the elements  
        from 1 to n+1 */
        for (int i = 2; i <= n + 1; i++) 
            x2 = x2 ^ i; 

    return (x1 ^ x2);

Question 16

Merge Sorted arrays without extra space

Answer 16

we take last as end of arr1
and for i > 1 till all elements of second array we find a place in the first array and replace it

for (int i=n-1; i>=0; i--)  
        {  
            /* Find the smallest element greater than ar2[i]. Move all  
            elements one position ahead till the smallest greater  
            element is not found */
            int j, last = arr1[m-1];  
            for (j=m-2; j >= 0 && arr1[j] > arr2[i]; j--)  
                arr1[j+1] = arr1[j];  

            // If there was a greater element  
            if (j != m-2 || last > arr2[i])  
            {  
                arr1[j+1] = arr2[i];  
                arr2[i] = last;  
            }  
        }

Question 17

Rearrange alternatively

Answer 17

idea is to use a multiplication and modular trick
have tow variables min and max index
and get the maximum element + 1

now for loop all elements
if even 
arr[i] = (arr[max_index--]%maxelement)*maxelement
else
arr[i] = (arr[min_index--]%maxelement)

*maxelement

now for loop each element / maxelement

Question 18

Inversion of array nversion count indicates how far (or close) the array is from being sorted.

Answer 18

simple method
foreach element count the elements to right of it and smaller

enhance mergesort

in merge sort we return invert count
when we merge we check if arr[i] < arr[j]

if greater then invertcount += mid - i

because then all the elements right to it are not in order so they need to be shifted

Question 19

Sort and array of 0, 1 , 2

Answer 19

easy problem maintain a switch case
for each elements i have a low mid and high pointer
if check for mid
if 0 replace with 0 and mid++ low++
if 1 continue
if 2 replace with 2 high-- 

or easier version we can just
count the number of 0, 1, 2
and put them in place
no need to reverse then

Question 20

Equilibrium index of an array

Equilibrium index of an array is an index such that the sum of elements at lower indexes is equal to the sum of elements at higher indexes.

Answer 20

simple 
for each point check suim of elements to the left
and elements to the right
if sum is greater then return true 
do this for each element

tricky approach

we calculate the whole sum
 then for each element
sum = sum - arr[i]
we check if left == sum
return if true
else leftsum  += arr[i]

return -1 if not found
Time Complexity: O(n)

Question 21

leaders in an array

Answer 21

easiest way is to for each element we could find if it is greater than all the elements right to it but it become polynomial

we can start from last and update right max if element found is greater than rgight max it is the leader at that time

Question 22

Minimum platforms required

Answer 22

sort the arrival and departure array
this makes its tc nlogn
now for every element in both array we check which one is smalles andbelongs to which array
so if arrival is smaller then we need more platforms
and the this platform if increase to max platforms update the max platforms else decrease the plat needed at that time
and increase counter of departure aray