Arrays Flashcards
Array Questions for Data structures
Reverse Array in groups
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--]);
} }
K’th smallest element
using heaps (TODO)
Trapping Rain Water
- 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)
Pythagorean triplet
1.Sort the Array
2. find the square of two numbers using meet in the middle alg
o(n^2)
Chocolate Distribution Problem
goal is to find the min diff among n packets
- Sort the array
- calculate the diff between i and i + k -1
- update if less than the minimum and store the start and end index
O(nlogn) sorting
Stock buy and sell
- Store the local minima (while arr[i + 1] < arr[i] ++)
- check if array last element (then not found after this)
- save local minima
- store local maxima
- Count++
Element with left side smaller and right side greater
- calculate left max array
- start with the end
- if element is greater than left max and less than right min update
o(n)
Convert array into Zig-Zag fashion
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
Last Index of 1
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)
Spirally traversing a matrix
maintain four index which serves as start and end indices of the row and columns
respectively increase/ decrease the rows and columns
Largest Number formed from an Array
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
SubArray with given sum
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;
Count the triplets
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];
}
Kadanes algo
Maximum subarray sum contiguous
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);
}
Missing number in array
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);
Merge Sorted arrays without extra space
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;
}
}
Rearrange alternatively
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
Inversion of array nversion count indicates how far (or close) the array is from being sorted.
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
Sort and array of 0, 1 , 2
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
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.
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)
leaders in an array
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
Minimum platforms required
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
