Introduction To
Arrays
An array is collection of items stored at contiguous memory locations. The idea is to store multiple items of same type together. This makes it easier to calculate the position of each element by simply adding an offset to a base value, i.e., the memory location of the first element of the array (generally denoted by the name of the array).
After the array is created, the values can be assigned. There are different ways to declare, create, and assign arrays.
Array elements are numbered starting with zero, which may seem confusing at first but is an important detail for many programming languages. The first element is at position [0], the second is at [1], and so on. The position of each element is determined by its offset from the start of the array.
Course Structure
Array Introduction
Array Rotations
- Program for array rotation
- Reversal algorithm for array rotation
- Block swap algorithm for array rotation
- Program to cyclically rotate an array by one
- Search an element in a sorted and rotated array
- Given a sorted and rotated array, find if there is a pair with a given sum
- Find maximum value of Sum( i*arr[i]) with only rotations on given array allowed
- Maximum sum of i*arr[i] among all rotations of a given array
- Find the Rotation Count in Rotated Sorted array
- Quickly find multiple left rotations of an array | Set 1
- Find the minimum element in a sorted and rotated array
- Reversal algorithm for right rotation of an array
- Find a rotation with maximum hamming distance
- Queries on Left and Right Circular shift on array
- Print left rotation of array in O(n) time and O(1) space
- Find element at given index after a number of rotations
- Split the array and add the first part to the end
Arrangement Rearrangement
- Rearrange an array such that arr[i] = i
- Write a program to reverse an array or string
- Rearrange array such that arr[i] >= arr[j] if i is even and arr[i]<=arr[j] if i is odd and j < i
- Rearrange positive and negative numbers in O(n) time and O(1) extra space
- Rearrange array in alternating positive & negative items with O(1) extra space | Set 1
- Move all zeroes to end of array
- Move all zeroes to end of array | Set-2 (Using single traversal)
- Minimum swaps required to bring all elements less than or equal to k together
- Rearrange positive and negative numbers using inbuilt sort function
- Rearrange array such that even positioned are greater than odd
- Rearrange an array in order – smallest, largest, 2nd smallest, 2nd largest, ..
- Double the first element and move zero to end
- Reorder an array according to given indexes
- Rearrange positive and negative numbers with constant extra space
- Arrange given numbers to form the biggest number | Set 1
- Rearrange an array such that ‘arr[j]’ becomes ‘i’ if ‘arr[i]’ is ‘j’ | Set 1
- Rearrange an array in maximum minimum form | Set 1
- Rearrange an array in maximum minimum form | Set 2 (O(1) extra space)
- Move all negative elements to end in order with extra space allowed
- Rearrange array such that even index elements are smaller and odd index elements are greater
- Positive elements at even and negative at odd positions (Relative order not maintained)
- Replace every array element by multiplication of previous and next
- Shuffle a given array using Fisher–Yates shuffle Algorithm
- Segregate even and odd numbers | Set 3
Order Statistics
- K’th Smallest/Largest Element in Unsorted Array | Set 2 (Expected Linear Time)
- K’th Smallest/Largest Element in Unsorted Array | Set 3 (Worst Case Linear Time)
- K’th Smallest/Largest Element using STL
- Kth smallest element in a row-wise and column-wise sorted 2D array | Set 1
- Program to find largest element in an array
- Find the largest three elements in an array
- Find all elements in array which have at-least two greater elements
- Program for Mean and median of an unsorted array
- K maximum sums of overlapping contiguous sub-arrays
- K maximum sums of non-overlapping contiguous sub-arrays
- k smallest elements in same order using O(1) extra space
- Find k pairs with smallest sums in two arrays
- k-th smallest absolute difference of two elements in an array
- Find Second largest element in an array
- Find the smallest and second smallest elements in an array
- Find the smallest missing number
- Maximum sum such that no two elements are adjacent
- Maximum and minimum of an array using minimum number of comparisons
Range Queries
- MO’s Algorithm (Query Square Root Decomposition) | Set 1 (Introduction)
- Sqrt (or Square Root) Decomposition Technique | Set 1 (Introduction)
- Sparse Table
- Range sum query using Sparse Table
- Constant time range add operation on an array
- Queries for GCD of all numbers of an array except elements in a given range
- Number of elements less than or equal to a given number in a given subarray
- Number of elements less than or equal to a given number in a given subarray | Set 2 (Including Updates)
- Queries for counts of array elements with values in given range
- Queries for decimal values of subarrays of a binary array
- Count elements which divide all numbers in range L-R
- Number whose sum of XOR with given array range is maximum
- XOR of numbers that appeared even number of times in given Range
- Array range queries over range queries
- Array range queries for searching an element
- Array range queries for elements with frequency same as value
- Number of indexes with equal elements in given range
- Total numbers with no repeated digits in a range
- Difference Array | Range update query in O(1)
Segment Tree
Self-Balancing BSTs
Optimization Problems
- Largest Sum Contiguous Subarray
- Maximum profit by buying and selling a share at most twice
- Find the subarray with least average
- Find the minimum distance between two numbers
- Minimize the maximum difference between the heights
- Minimum number of jumps to reach end
- Maximum Sum Increasing Subsequence | DP-14
- Smallest subarray with sum greater than a given value
- Find maximum average subarray of k length
- Count minimum steps to get the given desired array
- Number of subsets with product less than k
- Find minimum number of merge operations to make an array palindrome
- Find the smallest positive integer value that cannot be represented as sum of any subset of a given array
- Size of The Subarray With Maximum Sum
- Find minimum difference between any two elements
- Space optimization using bit manipulations
- Longest Span with same Sum in two Binary arrays
Sorting
- Alternative Sorting
- Sort an array in wave form
- Merge an array of size n into another array of size m+n
- Sort an array which contain 1 to n values
- Sort 1 to N by swapping adjacent elements
- Sort an array containing two types of elements
- Sort elements by frequency | Set 1
- Count Inversions in an array | Set 1 (Using Merge Sort)
- Two elements whose sum is closest to zero
- Shortest Un-ordered Subarray
- Minimum number of swaps required to sort an array
- Union and Intersection of two sorted arrays
- Find Union and Intersection of two unsorted arrays
- Sort an array of 0s, 1s and 2s
- Find the Minimum length Unsorted Subarray, sorting which makes the complete array sorted
- Count the number of possible triangles
- Find number of pairs (x, y) in an array such that x^y > y^x
- Count all distinct pairs with difference equal to k
- Construct an array from its pair-sum array
- Merge two sorted arrays with O(1) extra space
- Product of maximum in first array and minimum in second
Searching
- Search, insert and delete in an unsorted array
- Search, insert and delete in a sorted array
- Searching in an array where adjacent differ by at most k
- Find common elements in three sorted arrays
- Find position of an element in a sorted array of infinite numbers
- Find the element that appears once in an array where every other element appears twice
- Maximum Subarray Sum Excluding Certain Elements
- Maximum equlibrium sum in an array
- Equilibrium index of an array
- Leaders in an array
- Ceiling in a sorted array
- Majority Element
- Check for Majority Element in a sorted array
- Check if an array has a majority element
- Two Pointers Technique
- Find a peak element
- Find the two repeating elements in a given array
- Find a Fixed Point (Value equal to index) in a given array
- Find subarray with given sum | Set 1 (Nonnegative Numbers)
- Maximum triplet sum in array
- Smallest Difference Triplet from Three arrays
- Find a triplet that sum to a given value
Misc
- Subarray/Substring vs Subsequence and Programs to Generate them
- A Product Array Puzzle
- Number of subarrays with given product
- Check if array elements are consecutive | Added Method 3
- Find relative complement of two sorted arrays
- Minimum increment by k operations to make all elements equal
- Minimize (max(A[i], B[j], C[k]) – min(A[i], B[j], C[k])) of three different sorted arrays