Skip to main content

array

Array -#

  • problems - search, insert and delete; reverse an array; check for pair in A[] with sum as x; Majority Element; Largest Sum Contiguous Subarray; Search an element in a sorted and pivoted array; array rotation; Subarray with given sum ;

  • Always write base cases first; Like for 1 item in array, how would it do and then in some cases, 2 items when comparing

  • using two pointer technique, the array must be sorted. Take two pointers which mark the beginning and end of the array respectively and then move them.

  • create a temp array - solves the problem but adds to the space complexity

  • swap elements using indices and thus reducing the time complexity

  • increase the count when same element; when different, decrement the count (majority element)

  • storing 2 numbers in one number n1, n2 (make sure you have have n3 always greater than n1 and n2)

    num = (n3*n1) + n2

    use of this in https://www.geeksforgeeks.org/rearrange-array-maximum-minimum-form-set-2-o1-extra-space/

  • reverse first part of array, then reverse 2nd part, then reverse all. (array rotation)

  • keeping 3 pointers - low, mid and high : National Dutch flag problem

  • scan from right

  • XOR operator(^) - if different bits then 1, if same then 0 0^0 = 0 1^0 = 1 5^5 = 0 6^5 = 1 6^5^6 = 5

https://www.geeksforgeeks.org/find-the-number-occurring-odd-number-of-times/

  • Square Root Decompositions, Divide the array of size n into different blocks of √n each. (optimisation)

  • for a binary matrix you can calculate the number using base 2

  • Boyer-Moore Majority Voting Algorithm : find the majority element among the given elements that have more than N/ 2 occurrences;Increase the count when same, and decrease when different and when zero update the currentItem

  • kepping one pointer at first index and one at last, then move both in opposite direction until they meet. Using this 2 pointer approach to also find Quadruplet and triplet element sum in an array (using one extra for loop).

  • making use of quick sort intial partition to solve e.g Rearrange positive and negative numbers in O(n) time and O(1) extra space

  • creating a BST as we traverse the array elelments (may be self-balancing BST) and then doing sometuhing with it. This approach can be thought of when we need space , rather thn using a simple hash map.

  • using divide and conquer on the array, using the Binary search method e.g Find a peak element

  • create a K array of size, and increment the count when find same element, decrease it when found different; we can adjust the space complexity.

  • valley peak approach

    • Stock Buy and Sell
    • Maximum Subarray Sum
    • Trapping Rainwater

  • Make 2 math equations, for finding duplicates - sum of numbers, sum of squares of numbers, OR product of numbers in array.

  • using self balancing BST (red-blcak, OR Avl tree) - tree is always balanced, meaning height of left and right subtree can only differ by 1; this takes extra space of n

  • imp. sliding window (use this when subarray is involved) - https://www.geeksforgeeks.org/find-subarray-with-given-sum/

  • also we can use the sliding window technique when the size of the window is not fixed. (Smallest Subarray with a given sum)

  • fast and slow pointer approach - (moving one by single step and other by double step, they are going to meet) can be used to detect cycle anywhere. e.g happy number problem src - https://www.geeksforgeeks.org/happy-number/

  • finding top kth elements can be solved by using max heap or min heap.

  • If an array of n size has a number range from 1 to n, cyclic sort can be used to solve this. Try placing the number at the correct index.

  • if given an array of intervals, try sorting them using start time; Use merge interval technique.

  • Kadanes algorithm to find the subarray sum maximum : The algorithm keeps track of the maximum sum found so far and the maximum sum ending at each position as it traverses the array.

  • imp. Using modified merge sort to find reverse pairs in an array. - https://www.geeksforgeeks.org/inversion-count-in-array-using-merge-sort/

  • Whenever you're trying to solve an array problem in-place, always consider the possibility of iterating backwards instead of forwards through the array. It can completely change the problem, and make it a lot easier.

  • Binary search in sorted array

let mid = parseInt((left+right)/2);findPosition(nums, target, left, mid);findPosition(nums, target, mid+1, right);