Arrays Flashcards
(EASY) Shortest Unsorted Continuous Subarray
Given an integer array, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order, too. You need to find the shortest such subarray and output its length.
Example 1:
Input: [2, 6, 4, 8, 10, 9, 15]
Output: 5
Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.
https://leetcode.com/problems/shortest-unsorted-continuous-subarray/solution/
The idea behind this method is that the correct position of the minimum element in the unsorted subarray helps to determine the required left boundary. Similarly, the correct position of the maximum element in the unsorted subarray helps to determine the required right boundary.
- Find the minimum element after the unsorted array begins while iterating the array from the front.
- Find the maximum element after the unsorted array begins while iterating the array from the back.
- Find the index where this minimum element would go in the sorted array by iterating the array from the front again, which would be L. ie. Find the index of the first element which is just larger than min.
- Find the index where this maximum element would go in the sorted array by iterating the array from the back again, which would be R. ie. Find the index of the first element which is just smaller than max from backward.
Res: R-L+1
(Easy) Non-decreasing Array
Given an array nums with n integers, your task is to check if it could become non-decreasing by modifying at most 1 element.
We define an array is non-decreasing if nums[i] <= nums[i + 1] holds for every i (0-based) such that (0 <= i <= n - 2).
Example 1:
Input: nums = [4,2,3]
Output: true
Explanation: You could modify the first 4 to 1 to get a non-decreasing array.
https://leetcode.com/problems/non-decreasing-array/
for(int i=0; i < nums.size()-1; i++){
if(nums[i]>nums[i+1] && nums[i+1]>=nums[i-1]){
count++;
nums[i] = nums[i-1];
}
if(nums[i]>nums[i+1] && nums[i+1]<=nums[i-1]){
count++;
nums[i+1]=nums[i];
}
}
(Easy) K-diff Pairs in an Array
Given an array of integers and an integer k, you need to find the number of unique k-diff pairs in the array. Here a k-diff pair is defined as an integer pair (i, j), where i and j are both numbers in the array and their absolute difference is k.
Example 1:
Input: [3, 1, 4, 1, 5], k = 2 Output: 2 Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5). Although we have two 1s in the input, we should only return the number of unique pairs.
1. Time: O(n) , Space: O(n) if(k \< 0) return 0; int res=0; HashMap idxMap = new HashMap();
for(int i=0;i < nums.length;i++){
if(idxMap.get(nums[i])==null){
idxMap.put(nums[i],1);
}
else idxMap.put(nums[i], idxMap.get(nums[i])+1);
}
for(Integer i: idxMap.keySet()){
if(k==0){
if(idxMap.get(i) > 1) res++;
}
else{
if(idxMap.containsKey(i+k)) res++;
}
}
return res;
2: Time: O(nlogn)
Sort and check diff
(Easy) Best Time to Buy and Sell Stock II
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).
Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).
Input: [7,1,5,3,6,4]
Output: 7
Logic: 2 pointers L & R. keep increasing R, as the array slope keeps increasing. whenever there is a decrease add the price diff between L & R-1 and reset L to this current position and continue.
public int maxProfit(int[] prices) {
int sum=0;
int l=0;int r;
for(r=1; r < prices.length;r++){
if(prices[r] < prices[r-1]){
sum+= prices[r-1] - prices[l];
l=r;
}
}
sum+= prices[r-1] - prices[l];
return sum;
}
(Easy) Best Time to Buy and Sell Stock
If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Note that you cannot sell a stock before you buy one.
Example 1:
Input: [7,1,5,3,6,4] Output: 5
Maintain minPrice & maxProfit as you traverse the array.
Reasoning: Keep updating the bestPrice at which you can buy and keep updating the maxProfits with this lowest price, until you come across a further lower buyPrice, then check the maxProfits with this new lower price.
public int maxProfit(int[] prices) {
int minBuy = Integer.MAX_VALUE;
int maxProfit = Integer.MIN_VALUE;
for(int i=0;i < prices.length;i++){
if(prices[i] < minBuy)
minBuy=prices[i];
if(prices[i]-minBuy > maxProfit)
maxProfit = prices[i]-minBuy;
}
return maxProfit!=Integer.MIN_VALUE? maxProfit:0 ;
}
(Easy) Maximum Subarray
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Example:
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Thought:
dp[i+1] = max( dp[i], max_sum ending at i+1)
- we can either not include current element in the sum
- or take the max sum ending at current element.
max(1,2)
public int maxSubArray(int[] nums) {
if(nums.length==0) return 0;
int max=nums[0];
int max_ending_here=nums[0];
for(int r=1;r < nums.length;r++){
max_ending_here = Math.max(max_ending_here+nums[r], nums[r]);
max = Math.max(max, max_ending_here);
}
return max;
}
(Medium) Subarray Sums Divisible by K
Given an array A of integers, return the number of (contiguous, non-empty) subarrays that have a sum divisible by K.
Example 1:
Input: A = [4,5,0,-2,-3,1], K = 5
Output: 7
Explanation: There are 7 subarrays with a sum divisible by K = 5: [4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]
As is typical with problems involving subarrays, we use prefix sums to add each subarray. Let P[i+1] = A[0] + A[1] + … + A[i].
Then, each subarray can be written as P[j] - P[i] (for j > i). Thus, we have P[j] - P[i] equal to 0 modulo K, or equivalently P[i] and P[j] are the same value modulo K.
int[] sum = new int[A.length+1];
int res=0; int[] rems= new int[K];
for(int i=0; i < A.length;i++)
sum[i+1] = sum[i]+A[i];
for(int i=0; i < sum.length;i++)
rems[(sum[i]%K+K)%K]++;
for(int i=0; i < K;i++)
res+= (rems[i])*(rems[i]-1)/2;
return res;
(Medium) Container With Most Water
Given n non-negative integers a1, a2, …, an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container and n is at least 2.
So start with the first and last element and check the amount of water that can be contained and store that container.
Now the question arises is there any better boundaries or lines that can contain maximum water.
So there is a clever way to find that. Initially, there are two indices the first and last index pointing to the first and the last element (which acts as boundaries of the container), if the value first index is less than the last index increase the first index else decrease the last index.
int l = 0;
int r = height.length -1;
int area = 0;
while (l < r)
{
area = Math.max(area,
Math.min(height[l], height[r]) * (r - l));
if (height[l] <= height[r])
l += 1;
else
r -= 1;
}
return area;
(Medium) Number of Matching Subsequences
Given string S and a dictionary of words words, find the number of words[i] that is a subsequence of S.
Example :
Input: S = “abcde”
words = [“a”, “bb”, “acd”, “ace”]
Output: 3
Explanation: There are three words in words that are a subsequence of S: “a”, “acd”, “ace”.
Brute Force:
O( W * (S+L) )
Indexing + Binary Search:
O( W * L * log(S) )
Index character of String s into –> Map>indexes;
a-> [0 ,1,3]
b-> [2]
For each word –>
- For each letter find the smallest next possible index in the list which is greater than prev by binary search
int prev=-1;
for(int i=0;i < w.length();i++){
int idx = getFirstIdx(positions.get(w.charAt(i)), prev);
if(idx==-1)
return false;
prev = idx;
}
return true;
public int getFirstIdx(List list, int p){
if (list == null || list.size() == 0) return -1;
int low = 0;
int high=list.size()-1;
if(p>=list.get(high)) return -1;
while(low < high) {
int mid = (low+high)/2;
if(p >= list.get(mid))
low=mid+1;
else
high=mid;
}
return list.get(low);
}
(Medium) (DP) Maximum Length of Repeated Subarray
Given two integer arrays A and B, return the maximum length of an subarray that appears in both arrays.
Example 1:
Input: A: [1,2,3,2,1] B: [3,2,1,4,7] Output: 3 Explanation: The repeated subarray with maximum length is [3, 2, 1].
Since a common subarray of A and B must start at some A[i] and B[j], let dp[i][j] be the longest common prefix of A[i:] and B[j:]. Whenever A[i] == B[j], we know dp[i][j] = dp[i+1][j+1] + 1. Also, the answer is max(dp[i][j]) over all i, j.
public int findLength(int[] A, int[] B) {
int ans = 0;
int[][] dp=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])
dp[i][j]=1+dp[i+1][j+1];
if(ans < dp[i][j])
ans=dp[i][j];
}
}
return ans;
}
(Medium) Maximum Product Subarray
Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.
Example 1:
Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
public int maxProduct(int[] nums) {
if (nums.length == 0) return 0;
int max_so_far = nums[0];
int min_so_far = nums[0];
int result = max_so_far;
for (int i = 1; i < nums.length; i++) {
int curr = nums[i];
int temp_max = Math.max(curr, Math.max(max_so_far * curr, min_so_far * curr));
min_so_far = Math.min(curr, Math.min(max_so_far * curr, min_so_far * curr));
max_so_far = temp_max;
result = Math.max(max_so_far, result);
}
return result;
}
(Medium) Merge Intervals
Given a collection of intervals, merge all overlapping intervals.
Example 1:
Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
Sort with custom Comparator
class IntervalComparator implements Comparator{
@Override
public int compare(int[] a, int[] b) {
return a[0] \< b[0] ? -1 : a[0] == b[0] ? 0 : 1;
}
}
public int[][] merge(int[][] intervals) {
Collections.sort(Arrays.asList(intervals), new IntervalComparator());
List res = new ArrayList();
if(intervals.length==0) return intervals;
int start = intervals[0][0];int end = intervals[0][1];
for(int[] col: intervals){
if (col == intervals[0]) continue;
if(col[0] > =start && col[0] < =end)
end = Math.max(end,col[1]);
else{
res.add(new int[]{start,end});
start = col[0]; end = col[1];
}
}
res.add(new int[]{start,end});
arr = res.toArray(new int[res.size()][2]);
return arr;
}
(Medium) Subarray Product Less Than K
Given an array of positive integers nums.
Count and print the number of (contiguous) subarrays where the product of all the elements in the subarray is less than k.
Example 1:
Input: nums = [10, 5, 2, 6], k = 100
Output: 8
Explanation: The 8 subarrays that have product less than 100 are: [10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6]. Note that [10, 5, 2] is not included as the product of 100 is not strictly less than k.
Our loop invariant is that left is the smallest value so that the product in the window prod = nums[left] * nums[left + 1] * … * nums[right] is less than k.
For every right, we update left and prod to maintain this invariant. Then, the number of intervals with subarray product less than k and with right-most coordinate right, is right - left + 1. We’ll count all of these for each value of right.
public int numSubarrayProductLessThanK(int[] nums, int k) {
if (k < = 1) return 0;
int prod = 1, ans = 0, left = 0;
for (int right = 0; right < nums.length; right++) {
prod *= nums[right];
while (prod > = k) prod /= nums[left++];
ans += right - left + 1;
}
return ans;
}
(Medium) Minimum Size Subarray Sum
Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn’t one, return 0 instead.
Example:
Input: s = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: the subarray [4,3] has the minimal length under the problem constraint.
Sliding Window
public int minSubArrayLen(int s, int[] nums) {
int l=0; int sum=0;
int res=Integer.MAX_VALUE;
int r;
boolean flag=false;
for(r=0; r < nums.length;r++){
sum+=nums[r];
if(sum > =s){
flag=true;
while(sum > =s) sum-=nums[l++];
res = Math.min(res,r-l+2);
}
}
return flag? res : 0;
}
(Medium) 4Sum
Given an array of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Note:
The solution set must not contain duplicate quadruplets.
Example:
Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.
A solution set is: [[-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]
Sort the Array
Hashmap with counts
n^3 loop and two sum at the end.
public List<list>> fourSum(int[] nums, int target) {<br></br> List<list>> res = new ArrayList<>(); <br></br> if(nums==null || nums.length<4)<br></br> return res;</list></list>
Arrays.sort(nums);
HashMap<integer integer> cnt = new HashMap();<br> <br> for(int i=0; i < nums.length;i++){<br> if(cnt.get(nums[i])==null) cnt.put(nums[i],1);<br> else cnt.put(nums[i],cnt.get(nums[i])+1);<br> }<br> for(int i=0; i < nums.length-3;i++){<br> if(i!=0 && nums[i]==nums[i-1])<br> continue;<br> for(int j=i+1; j < nums.length-2;j++){<br> if(j!=i+1 && nums[j]==nums[j-1])<br> continue;<br> for(int k=j+1; k < nums.length-1;k++){<br> if(k!=j+1 && nums[k]==nums[k-1])<br> continue;<br> int check = target-(nums[i]+nums[j]+nums[k]);<br> if(cnt.containsKey(check)){<br> int val = cnt.get(check);<br> if(check == nums[i]) val--;<br> if(check == nums[j]) val--;<br> if(check == nums[k]) val--;<br> if(val > 0 && check > =nums[k])<br> res.add(Arrays.asList(nums[i],nums[j],nums[k],check));<br> }<br> }<br> }<br> }<br> return res;<br> }</integer>
