Arrays Flashcards
Subarray Sum Equals K
The idea behind this approach is as follows: If the cumulative sum(represented by sum[i]sum[i] for sum up to i^{th}) up to two indices is the same, the sum of the elements lying in between those indices is zero. Extending the same thought further, if the cumulative sum up to two indices, say i and j is at a difference of k i.e. if sum[i] - sum[j] = k , the sum of elements lying between indices i and j is k.
Based on these thoughts, we make use of a hashmap map which is used to store the cumulative sum up to all the indices possible along with the number of times the same sum occurs. We store the data in the form: (sum_i, no. of occurrences of sum_i).
We traverse over the array nums and keep on finding the cumulative sum. Every time we encounter a new sum, we make a new entry in the hashmap corresponding to that sum. If the same sum occurs again, we increment the count corresponding to that sum in the hashmap. Further, for every sum encountered, we also determine the number of times the sum−k has occurred already, since it will determine the number of times a subarray with sum k has occurred up to the current index. We increment the count by the same amount.
After the complete array has been traversed, the count gives the required result.
public class Solution {
public int subarraySum(int[] nums, int k) {
int count = 0, sum = 0;
HashMap < Integer, Integer > map = new HashMap < > ();
map.put(0, 1);
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
if (map.containsKey(sum - k))
count += map.get(sum - k);
map.put(sum, map.getOrDefault(sum, 0) + 1);
}
return count;
}
}
maximum sum subarray
class Solution {
public int maxSubArray(int[] nums) {
// Initialize our variables using the first element.
int currentSubarray = nums[0];
int maxSubarray = nums[0];
// Start with the 2nd element since we already used the first one.
for (int i = 1; i < nums.length; i++) {
int num = nums[i];
// If current_subarray is negative, throw it away. Otherwise, keep adding to it.
currentSubarray = Math.max(num, currentSubarray + num);
maxSubarray = Math.max(maxSubarray, currentSubarray);
}
return maxSubarray; } }
Search in rotated sorted array
class Solution {
public int search(int[] nums, int target) {
int start = 0, end = nums.length - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (nums[mid] == target) return mid;
else if (nums[mid] >= nums[start]) {
if (target >= nums[start] && target < nums[mid]) end = mid - 1;
else start = mid + 1;
}
else {
if (target <= nums[end] && target > nums[mid]) start = mid + 1;
else end = mid - 1;
}
}
return -1;
}
}Pairs of Songs With Total Durations Divisible by 60
class Solution {
public int numPairsDivisibleBy60(int[] time) {
int remainders[] = new int[60];
int count = 0;
for (int t: time) {
if (t % 60 == 0) { // check if a%60==0 && b%60==0
count += remainders[0];
} else { // check if a%60+b%60==60
count += remainders[60 - t % 60];
}
remainders[t % 60]++; // remember to update the remainders
}
return count;
}
}Find First and Last Position of Element in Sorted Array
class Solution {
public int[] searchRange(int[] nums, int target) {
int firstOccurrence = this.findBound(nums, target, true);
if (firstOccurrence == -1) {
return new int[]{-1, -1};
}
int lastOccurrence = this.findBound(nums, target, false);
return new int[]{firstOccurrence, lastOccurrence};
}
private int findBound(int[] nums, int target, boolean isFirst) {
int N = nums.length;
int begin = 0, end = N - 1;
while (begin <= end) {
int mid = (begin + end) / 2;
if (nums[mid] == target) {
if (isFirst) {
// This means we found our lower bound.
if (mid == begin || nums[mid - 1] != target) {
return mid;
}
// Search on the left side for the bound.
end = mid - 1;
} else {
// This means we found our upper bound.
if (mid == end || nums[mid + 1] != target) {
return mid;
}
// Search on the right side for the bound.
begin = mid + 1;
}
} else if (nums[mid] > target) {
end = mid - 1;
} else {
begin = mid + 1;
}
}
return -1; } }
longest-consecutive-sequence
class Solution {
public int longestConsecutive(int[] nums) {
Set num_set = new HashSet();
for (int num : nums) {
num_set.add(num);
}
int longestStreak = 0;
for (int num : num_set) {
if (!num_set.contains(num-1)) {
int currentNum = num;
int currentStreak = 1;
while (num_set.contains(currentNum+1)) {
currentNum += 1;
currentStreak += 1;
}
longestStreak = Math.max(longestStreak, currentStreak);
}
}
return longestStreak;
} }
Maximum Length of Repeated Subarray
Given two integer arrays nums1 and nums2, return the maximum length of a subarray that appears in both arrays.
class Solution {
public int findLength(int[] A, int[] B) {
int ans = 0;
int[][] memo = new int[A.length + 1][B.length + 1];
for (int i = A.length - 1; i >= 0; --i) {
for (int j = B.length - 1; j >= 0; --j) {
if (A[i] == B[j]) {
memo[i][j] = memo[i+1][j+1] + 1;
if (ans < memo[i][j]) ans = memo[i][j];
}
}
}
return ans;
}
}Find peak element
public class Solution {
public int findPeakElement(int[] nums) {
int l = 0, r = nums.length - 1;
while (l < r) {
int left = Integer.MIN_VALUE;
int right = Integer.MIN_VALUE;
int mid = l + (r-l) / 2;
if(mid > l) {
left = nums[mid-1];
}
if(mid < r) {
right = nums[mid+1];
}
if (nums[mid] >= left && nums[mid] >= right) {
return mid;
}
if(nums[mid] < left) {
r = mid - 1;
}
else {
l = mid + 1;
}
}
return l;
}
}search-a-2d-matrix
input matrix m x n could be considered as a sorted array of length m x n.
Sorted array is a perfect candidate for the binary search because the element index in this virtual array (for sure we’re not going to construct it for real) could be easily transformed into the row and column in the initial matrix
row = idx // n and col = idx % n.
The algorithm is a standard binary search :
Initialise left and right indexes left = 0 and right = m x n - 1.
While left <= right :
Pick up the index in the middle of the virtual array as a pivot index : pivot_idx = (left + right) / 2.
The index corresponds to row = pivot_idx // n and col = pivot_idx % n in the initial matrix, and hence one could get the pivot_element. This element splits the virtual array in two parts.
Compare pivot_element and target to identify in which part one has to look for target.
Time complexity : O(log(m n)) since it’s a standard binary search.
Space complexity : O(1).
k diff pairs
public class Solution {
public int findPairs(int[] nums, int k) {
int result = 0;
HashMap counter = new HashMap<>();
for (int n: nums) {
counter.put(n, counter.getOrDefault(n, 0)+1);
}
for (Map.Entry entry: counter.entrySet()) {
int x = entry.getKey();
int val = entry.getValue();
if (k > 0 && counter.containsKey(x + k)) {
result++;
} else if (k == 0 && val > 1) {
result++;
}
}
return result;
}
}
generate random numbers between 2 numbers
int random(int lower, int higher){
return lower + (int)(Math.random() * (higher - lower + 1));
}
