Array Problems
For Arrays, Strings and Lists
- For Array, length is a field -
array.length - For String, length is a method -
str.length() - List length is a 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
int left = 0, right = str.length() - 1;
while(left < right){
left++;
right--;
}
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
One Fast runner the other one runs slow.
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];