Leetcode record - June 2023
624. Maximum Distance in Arrays
You are given m arrays, where each array is sorted in ascending order.
You can pick up two integers from two different arrays (each array picks one) and calculate the distance. We define the distance between two integers a and b to be their absolute difference |a - b|.
Return the maximum distance.
Example 1:
Input: arrays = [[1,2,3],[4,5],[1,2,3]] Output: 4 Explanation: One way to reach the maximum distance 4 is to pick 1 in the first or third array and pick 5 in the second array. Example 2:
Input: arrays = [[1],[1]] Output: 0
class Solution {
public int maxDistance(List<List<Integer>> arrays) {
int minVal = arrays.get(0).get(0);
int maxVal = arrays.get(0).get(arrays.get(0).size() - 1);
int maxDistance = 0; //very important. Can't be maxVal - minVal!
/*
For every new array, we calculate the distance in two ways:
Between the smallest element in this array and the maximum element seen so far in the previous arrays.
Between the largest element in this array and the minimum element seen so far in the previous arrays.
*/
for (int i = 1; i < arrays.size(); i++) {
List<Integer> array = arrays.get(i);
maxDistance = Math.max(maxDistance,
Math.max(Math.abs(maxVal - array.get(0)),
Math.abs(array.get(array.size() - 1) - minVal)));
minVal = Math.min(minVal, array.get(0));
maxVal = Math.max(maxVal, array.get(array.size() - 1));
}
return maxDistance;
}
}
- Sliding Window’s key word: array, consecutive.
159. Longest Substring with At Most Two Distinct Characters
Given a string s, return the length of the longest substring that contains at most two distinct characters.
Example 1:
Input: s = "eceba" Output: 3 Explanation: The substring is "ece" which its length is 3.
Example 2:
Input: s = "ccaabbb" Output: 5 Explanation: The substring is "aabbb" which its length is 5.
class Solution {
public int lengthOfLongestSubstringTwoDistinct(String s) {
int l = 0, r = 0;
HashMap <Character,Integer> hm = new HashMap<>();
int len = 0;
int maxlen = 0;
while(r<s.length()){
//put first and then handle conflict later
hm.put(s.charAt(r),hm.getOrDefault(s.charAt(r),0)+1);
//handle cpnflict
while(hm.size()>=3){
if(hm.get(s.charAt(l)) == 1){
hm.remove(s.charAt(l));
}else{
hm.put(s.charAt(l),hm.get(s.charAt(l)) - 1);
}
l++;
len--;
}
r++;
len++;
maxlen = Math.max(maxlen, len);
}
return maxlen;
}
}
Given a binary array nums, return the maximum number of consecutive 1’s in the array if you can flip at most one 0.
Example 1:
Input: nums = [1,0,1,1,0] Output: 4 Explanation:
If we flip the first zero, nums becomes [1,1,1,1,0] and we have 4 consecutive ones.If we flip the second zero, nums becomes [1,0,1,1,1] and we have 3 consecutive ones. The max number of consecutive ones is 4.
class Solution {
public int findMaxConsecutiveOnes(int[] nums) {
int l = 0, r = 0;
int []cnt = new int[2];
int maxlens = 0, lens = 0;
while(r<nums.length){
cnt[nums[r]]++;
while(cnt[0]>1){
cnt[nums[l]]--;
l++;
lens--;
}
r++;
lens++;
maxlens = Math.max(lens, maxlens);
}
return maxlens;
}
}
1100. Find K-Length Substrings With No Repeated Characters
Given a string s and an integer k, return the number of substrings in s of length k with no repeated characters.
Example 1:
Input: s = "havefunonleetcode", k = 5 Output: 6 Explanation: There are 6 substrings they are: 'havef','avefu','vefun','efuno','etcod','tcode'. Example 2:
Input: s = "home", k = 5 Output: 0 Explanation: Notice k can be larger than the length of s. In this case, it is not possible to find any substring.
class Solution {
public int numKLenSubstrNoRepeats(String s, int k) {
if(s.length()<k){
return 0;
}
HashMap<Character, Integer> hm = new HashMap<>();
int l = 0, r = 0;
int cnt = 0;
while(r<s.length()){
hm.put(s.charAt(r),hm.getOrDefault(s.charAt(r),0)+1);
while(hm.get(s.charAt(r))>=2){
hm.put(s.charAt(l),hm.get(s.charAt(l)) - 1);
l++;
}
r++;
if(r-l == k){
cnt++;
// Remember to change the Hashmap count
//whenever you change l or r variable.
hm.put(s.charAt(l),hm.get(s.charAt(l)) - 1);
l++;
}
}
return cnt;
}s
}