Arrays Flashcards
For circular sorted array , that has been rotated , what is the formula for finding the number of rotations?
Number of rotations=Number of elements before minimum element or
index of the minimum element
Reversal algorithm for array(size n) rotation on left side(anti clock wise) by d
rotate(arr[], d, n) reverse(arr[], 0, d-1) ; reverse(arr[], d, n-1); reverse(arr[], 0, n); why d-1 because array is zero based index
Reversal algorithm for array(size n) rotation right side(clock wise) by d
rotate(arr[], d, n) reverse(arr[], 0, n-1) ; reverse(arr[], 0, d-1); reverse(arr[], d, n-1); why d-1 because array is zero based index
If we know that array is sorted but don’t know how it is sorted (ascending or descending) than how will we know?
Compare first element with last element.
If first element < last element sorted in ascending
else sorted in descending order
What is transposing a matrix means ?
The transpose of a matrix is the matrix flipped over it's main diagonal, switching the row and column indices of the matrix.
for (int r = 0; r < rows; r++)
{
// ! initializing r with one more as swapping across the diagonal will transpose the matrix
// ! Not adding by one will give wrong result
for (int c = r + 1; c < columns; c++)
{
//! row becomes column and column become row acorss the diagonal
int temp = matrix[r][c];
matrix[r][c] = matrix[c][r];
matrix[c][r] = temp;
}
}How to calculate the pivot index and pivot element on 2D array that is sorted row by row?
pivot index will be calculated same way as in one dimensional array
pivotIndex=lo+((hi-lo)/2);
For pivot element, we will use below formula
pivotElement = matrix[pivotIndex/ columns][pivotIndex% columns];
where columns are number of columns
Why pivotIndex/columns or pivotIndex%columns because we are visualizing 2D array as 1D array
How to calculate pivot index for sorted array that has been rotated x number of times?
Pivot element will always be in the non-uniformly increasing part. We can do binary search to find out where in array we have non-uniformly increasing part.
private int FindPivotIndex(int[] nums)
{
int low = 0;
int pivotIndex = 0;
int high = nums.Length - 1;
//array is sorted already
if (nums[low] < nums[high])
return 0;
while (low < high)
{
pivotIndex = low + ((high - low) / 2);
//! pivot element is one having left element and right element less than it.
//! Comparing only on the right side is enough
if (nums[pivotIndex] > nums[pivotIndex + 1])
{
return pivotIndex;
}
// !Pivot element always present in the non uniformly increasing part
//! if first element is less than pivot index element than it means its strictly increasing
//! we need to search on right side as its non uniformly increasing part
else if (nums[low] < nums[pivotIndex])
{
low = pivotIndex + 1;
}
else
{
//! why pivotIndex and why not pivotIndex-1?
//!because element at pivot index can also be the part of the non uniformly increasing
high = pivotIndex;
}
}
return pivotIndex;
}
How to convert a 2-d array of size (m x n) into 1-d array and how to store the element at position [i, j] of 2-d array in 1-d array?
https://www.geeksforgeeks.org/emulating-a-2-d-array-using-1-d-array/ k =(i * total_no_of_columns_in_matrix)+j where k is 1d array index where i is the row index in 2D array where j is the column index in 2D array
Given 1-d array that maps to 2-d array. What is the formula for recalculation of 1D array indices into 2D array index ?
https://leetcode.com/problems/random-flip-matrix/
index/columns, index%columns
How to do round robin on dictionary with frequency as value and char as key sorted in descending by value and store them to buckets ? For example a:5 b:4 c:2 d:1
https://leetcode.com/problems/reorganize-string/
int i = 0;
foreach (KeyValuePair keyValue in frequencyCount)
{
for (int j = 0; j < keyValue.Value; ++j)
{
buckets[i % maxCount].Append(keyValue.Key);
++i;
}
}
Given an array of integers of size ‘n’. How to apply sliding window technique to calculate the maximum sum possible for ‘k’ consecutive elements in the array?
https://medium.com/leetcode-patterns/leetcode-pattern-2-sliding-windows-for-strings-e19af105316b int max_sum = 0, window_sum = 0; /* calculate sum of 1st window */ for (int i = 0; i < k; i++) window_sum += arr[i]; /* slide window from start to end in array. */
for (int i = k; i < n; i++){
window_sum += arr[i] - arr[i-k]; // saving re-computation
max_sum = max(max_sum, window_sum);
}
How to apply hare tortoise algorithm on array
https://leetcode.com/problems/find-the-duplicate-number/
int tortoise=nums[0];
int hare=nums[0];
do
{
tortoise=nums[tortoise];
hare=nums[nums[hare]];
} while(tortoise!=hare); hare=nums[0];
while(hare!=tortoise)
{
tortoise=nums[tortoise];
hare=nums[hare];
}
return hare;
How to know how many non-empty subarrays are there in an array?
https://www.youtube.com/watch?v=qoI26oy8MeI
N(N+1)/2
What is the difference between subarray , subsequence and subset?
https://www.youtube.com/watch?v=qoI26oy8MeI
Subarray: contiguous part of an array
Subsequence: May not be contiguous but maintain the relative order
Subset: May not be contiguous and may not be in order
How many non-empty subsequences in an array of size n?
https://www.youtube.com/watch?v=qoI26oy8MeI
2^n - 1
