Array Problems
For Arrays, Strings and Lists
- For Array, length is a field -
array.length
- For String, length is a method -
str.length()
- List has a size method =
list.size()
Single Pointer Technique
- Iterate through LEFT
- Iterate through RIGHT
int idx = arr.length-1
int idx = list.size()-1
- Use an ADDITIONAL ARRAY of same size (Space complexity O(N), where N = size of the array
- Optimize the additional Array to use a single variable
Two Pointer Technique
- One begins from left/start, other from the right end.
- The while loop
int left = 0, right = str.length() - 1; while(left < right){ left++; right--; }
- The for loop
for(int low = 0, high = s.length-1; low < high; low++,high--){
Left pointer and Right pointer movements based on if condition.
Find count of given Sum in all pairs in the Array
Checks
if (array size < 2)
return 0;
Approach 1 : Greedy approach to test all the possible combinations exhaustively
Approach 2 : Two pointer Approach - Test only those possible combinations that makes sense
Approach 3 : Hash map and variant approach
Left & Right Array approach
Create two temporary arrays,
- one left that takes computation of elements to the left, upto the current element.
- Same for Right array.
Replace each element with the greatest element to the Right in an Array
https://leetcode.com/problems/replace-elements-with-greatest-element-on-right-side/
Replace a number with product of all other without division
https://leetcode.com/problems/product-of-array-except-self/
Trapping Rain Water
left[i] = Math.max(left[i-1], arr[i]);//arr[i] means including current element
right[i] = Math.max(right[i+1], arr[i]);
result = result + Math.min(left[i],right[i]) - arr[i];