Arrays and Strings and HashMap(?)
ArrayList -> An array that resizes itself when still needed while still providing O(1) access. A typical implementation is that when the array is full, the array doubles in size. Each doubling takes O(n) time, but happen rarely that its armortized insertion time is O(1).
StringBuilder
StringBuilder is a beneficial class in Java for constructing and manipulating strings efficiently. Here are some benefits of using wordStringBuilder:
- Improved performance: Unlike String objects, which are immutable, StringBuilder objects are mutable, which means you can modify them without creating a new object. Thisro can improve performance when building or modifying strings because it avoids the overhead of creating multiple intermediate String objects.form
- Efficient memory usage: When you use String concatenation using the ‘+’ operator, a new String object is created each time, which can quickly consume memory if done frequently. With StringBuilder, you can append new characters or strings to an existing StringBuilder object, which reduces memory usage.
- Flexible and easy to use: StringBuilder provides methods for appending, inserting, deleting, and replacing characters and strings in a flexible and easy-to-use way. This makes it easy to manipulate strings and build them up incrementally.
Overall, StringBuilder is a useful class for constructing and manipulating strings in a performant and memory-efficient way, and it is a good choice when dealing with larger or more complex string manipulations.
StringBuilder sb = new StringBuilder("abc").append("de");
String str = sb.toString();
// Append a string
sb.append(" She sells sea shells by the sea shore.");
// Insert a string at a specific index
sb.insert(45, "quick ");
// Delete a range of characters
sb.delete(30, 34); // Removes "jumps"
// Replace a string with another string
sb.replace(49, 52, "smiles");Array -> 数组
Contiguous subarray -> 直数组
Element -> 元素
Sum -> 合, eg, 它们的合是。。。 Their sum is
右边端点，左边端点 Left index, right index
Common Techniques
Sliding Window Approach
A window is formed over some part of the data and this window can slide over the data to capture different portions of it. When a window slides, only two elements change. The oldest one drops off and the newest one comes into the frame.
In the brute force approach, the inefficient part is that for any two consecutive subarrays of size k, the overlapping part (which contains k-1 elements) is evaluated twice. By using the sliding window approach, we can get rid of that and calculate the sum in O(1) using the sum of previous consecutive subarray.
You can also implement the sliding window approach with two pointers left & right as the following code.
The time complexity is then linear O(n) as we only need one loop.
left = 0
right = 0
while right < n:
window.add(s[right])
right += 1
while (condition):
window.remove(s[left])
left += 1Creating a character array to keep track of the occurrences of each character
int[] counter(String word) {
int[] count = new int[26];
for (char c : word.toCharArray()) count[c - 'a']++;
return count;
}Counting inversions
Use Merge sort
Leetcode 775
775. Global and Local Inversions
You are given an integer array nums of length n which represents a permutation of all the integers in the range [0, n - 1].
The number of global inversions is the number of the different pairs (i, j) where:
0 <= i < j < nnums[i] > nums[j]
The number of local inversions is the number of indices i where:
0 <= i < n - 1nums[i] > nums[i + 1]
Return true if the number of global inversions is equal to the number of local inversions.
Example 1:
Input: nums = [1,0,2]
Output: true
Explanation: There is 1 global inversion and 1 local inversion.Example 2:
Input: nums = [1,2,0]
Output: false
Explanation: There are 2 global inversions and 1 local inversion.class Solution {
public boolean isIdealPermutation(int[] nums) {
// local: Compare to the one next to you
// global: Compare to the list of nums on your right
int local = computeLocal(nums);
int global = computeGlobal(nums);
return local == global;
}
public int computeGlobal(int[] nums){
return mergeSort(nums, 0, nums.length-1);
}
public int mergeSort(int[] nums, int start, int end){
int count = 0;
if(start < end){
int mid = (start+end)/2;
count = mergeSort(nums, start, mid);
count += mergeSort(nums, mid+1, end);
count += merging(nums, start, mid+1, end);
}
return count;
}
public int merging(int[] nums, int start, int mid, int end){
int[] copy = new int[nums.length];
for(int k=start; k<=end; k++){
copy[k] = nums[k];
}
int count = 0;
int i=start;
int j=mid;
int idx=start;
while(i<mid && j<=end){
if(copy[i]<=copy[j]){
nums[idx]=copy[i];
i++;
} else {
nums[idx]=copy[j];
j++;
count+=(mid-i);
}
idx++;
}
while(i<mid){
nums[idx]=copy[i];
idx++;
i++;
}
while(j<=end){
nums[idx]=copy[j];
j++;
idx++;
}
return count;
}
public int computeLocal(int[] nums){
int count = 0;
for(int i=1; i<nums.length; i++){
if(nums[i] < nums[i-1]) count++;
}
return count;
}
}
// Time limit exceeded..Accepted solution
Approach #2: Remember Minimum [Accepted]
Intuition
In performing a brute force, we repeatedly want to check whether there is some j >= i+2 for which A[i] > A[j]. This is the same as checking for A[i] > min(A[i+2:]). If we knew these minimums min(A[0:]), min(A[1:]), min(A[2:]), ... we could make this check quickly.
Algorithm
Let’s iterate through A from right to left, remembering the minimum value we've seen. If we remembered the minimum floor = min(A[i:]) and A[i-2] > floor, then we should return False. This search is exhaustive, so if we don't find anything after iterating through A, we should return True.
public boolean isIdealPermutation(int[] A) {
int N = A.length;
int floor = N;
for (int i=N-1; i>=2; --i) {
floor = Math.min(floor, A[i]);
if (A[i-2] > floor) return false;
}
return true;
}Complexity Analysis
- Time Complexity: O(N), where N is the length of
A. - Space Complexity: O(1).
TODO: https://leetcode.com/problems/reverse-pairs/
315. Count of Smaller Numbers After Self
This is one of those questions that are simple enough to give you hope but are actually an omega pain in the butt
You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].
Example 1:
Input: nums = [5,2,6,1]
Output: [2,1,1,0]
Explanation:
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.The optimal solution is to use MergeSort method to count.
We make use of 2 additional variables to help us. The first is int count[] which stores the result. The second is rightCount inside the merge method to help us in tracking number of right elements that is smaller than the current left element we are iterating.
QNS: What does int[] indexes mean?
Note that in merge, the items in the positions from [start…mid] and [mid+1…end] are already sorted internally. We term these two sorted portions to be LEFT and RIGHT.
In this merging, we are iterating through the indexes array. The p1, p2…indexes are the indexes of the elements in the LEFT and RIGHT respectively. We compare the values at those indexes p1, p2.
Here, we need to track its’ indexes and add to the new array depending on the values of these indexes (Doing merge sort on the index array and the basis of comparison is their values). We want to track the indexes because we need to edit count[] array.
** TDLR: We are only modifying the values in the indexes array. nums array remains unchanged.
Each time we add an element from the left side, we set the count[i] to be rightCount.
rightCount contains the number of elements on the right that is smaller than this current element on the left.
class Solution {
int[] count;
public List<Integer> countSmaller(int[] nums) {
List<Integer> res = new ArrayList<>();
count = new int[nums.length];
int[] indexes = new int[nums.length];
for(int i=0; i<nums.length; i++){
indexes[i]=i;
}
mergeSort(nums, indexes, 0, nums.length-1);
for(int i=0; i<count.length; i++){
res.add(count[i]);
}
return res;
}
public void mergeSort(int[] nums, int[] indexes, int start, int end){
if(start<end){
int mid = (start+end)/2;
mergeSort(nums, indexes, start, mid);
mergeSort(nums, indexes, mid+1, end);
merging(nums, indexes, start, mid+1, end);
}
}
// sort the index.....
// We want to know which index ends up in which position eventually.
public void merging(int[] nums, int[] index, int start, int mid, int end){
int i=start;
int j=mid;
int idx=0;
int rightCount = 0;
int[] newIndexes = new int[end-start+1];
// index[i] gives the original index of the number at i.
while(i<mid && j<=end){
// right smaller than left,
// index of current val will be moved leftward -> to indicate its' new position
if(nums[index[j]] < nums[index[i]]){
newIndexes[idx] = index[j];
rightCount++;
j++;
idx++;
} else {
// left smaller than right.
// This current number is bigger than all those numbers that were previously moved from right
// to left...hence the inversion count (rightcount) should be added to this particular number.
newIndexes[idx] = index[i];
count[index[i]] += rightCount;
i++;
idx++;
}
}
while(i<mid){
newIndexes[idx] = index[i];
count[index[i]] += rightCount;
idx++;
i++;
}
while(j<=end){
newIndexes[idx] = index[j];
idx++;
j++;
}
for(int k=start; k<=end; k++){
index[k] = newIndexes[k-start];
}
}
}Explanation from the LEETCODE (This is so confusing, i don’t really understand)
Intuition
Prerequisite: Merge Sort
If you are not familiar with Merge Sort, you should check relevant tutorials before continuing.
Also, here is a basic application of Merge Sort that you can practice on: Sort an Array
To apply merge sort, one key observation is that:
The smaller elements on the right of a number will jump from its right to its left during the sorting process.
class Solution {
public List<Integer> countSmaller(int[] nums) {
int n = nums.length;
int[] result = new int[n];
int[] indices = new int[n]; // record the index. we are going to sort this array
for (int i = 0; i < n; i++) {
indices[i] = i;
}
// sort indices with their corresponding values in nums, i.e., nums[indices[i]]
mergeSort(indices, 0, n, result, nums);
// change int[] to List to return
List<Integer> resultToReturn = new ArrayList<Integer>(n);
for (int i : result) {
resultToReturn.add(i);
}
return resultToReturn;
}
private void mergeSort(int[] indices, int left, int right, int[] result, int[] nums) {
if (right - left <= 1) {
return;
}
int mid = (left + right) / 2;
mergeSort(indices, left, mid, result, nums);
mergeSort(indices, mid, right, result, nums);
merge(indices, left, right, mid, result, nums);
}
private void merge(int[] indices, int left, int right, int mid, int[] result, int[] nums) {
// merge [left, mid) and [mid, right)
int i = left; // current index for the left array
int j = mid; // current index for the right array
// use temp to temporarily store sorted array
List<Integer> temp = new ArrayList<Integer>(right - left);
while (i < mid && j < right) {
if (nums[indices[i]] <= nums[indices[j]]) {
// j - mid numbers jump to the left side of indices[i]
result[indices[i]] += j - mid;
temp.add(indices[i]);
i++;
} else {
temp.add(indices[j]);
j++;
}
}
// when one of the subarrays is empty
while (i < mid) {
// j - mid numbers jump to the left side of indices[i]
result[indices[i]] += j - mid;
temp.add(indices[i]);
i++;
}
while (j < right) {
temp.add(indices[j]);
j++;
}
// restore from temp
for (int k = left; k < right; k++) {
indices[k] = temp.get(k - left);
}
}
}Let N be the length of nums.
- Time Complexity: O(Nlog(N)). We need to perform a merge sort which takes O(Nlog(N)) time. All other operations take at most O(N) time.
- Space Complexity: O(N), since we need a constant number of arrays of size O(N).
Heap Sort
Leetcode
27. Remove Element
Given an array nums and a value val, remove all instances of that value in-place and return the new length.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
The order of elements can be changed. It doesn’t matter what you leave beyond the new length.
Return the last index of the modified array.
Example 1:
Input: nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2]
Explanation: Your function should return length = 2, with the first two elements of nums being 2.
It doesn't matter what you leave beyond the returned length. For example if you return 2 with nums = [2,2,3,3] or nums = [2,3,0,0], your answer will be accepted.Example 2:
Input: nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5, nums = [0,1,4,0,3]
Explanation: Your function should return length = 5, with the first five elements of nums containing 0, 1, 3, 0, and 4. Note that the order of those five elements can be arbitrary. It doesn't matter what values are set beyond the returned length.
Leetcode 53. Q1 Given an array of integers, return the highest sum of any k consecutive elements in the array.
Wanted to use sliding window…but didn’t come up with a solution. So in the end, decide to use dynamic programming.
To remember how to solve this question, think of the sub problem:
- If i have the max sum of k consecutive elements from 0…i-1, and i am currently at index i, how do i make use of the results from prior? To form dp[i], how do i make use of dp[i-1]
- The first way we might think of is to have the 1D array, dp[i-1] contain the max sum of K consecutive elements from 0…...i–1, then decide whether to add curr element arr[i] to it or not. However, we soon realise that the element arr[i-1] might not have been included in the sum of dp[i-1]. Only when the previous element arr[i-1] has been added to dp[i-1], we can add arr[i] into the dp[i], otherwise it is not consecutive.
- Hence, we need a way to make it 100% correct for us to decide whether to add current element to dp[i].
- We then change our definition of what dp[i-1] contains.
- One way is to set the condition that dp[i-1] will always contain the maximum sum of elements from position i-1 (Ensure that the prev element is always added to the sum) to somewhere ≥ 0. Hence, in each iteration we are safe to append arr[i] to the sum of dp[i]. Then we can make it such that in each iteration, we are only deciding whether we want to add current element a[i] to dp[i-1] or start afresh with a[i]. We then have to keep track of the maximum sum by having a variable.
class Solution {
public int maxSubArray(int[] nums) {
// at each index, you either include yourself to the prev or start a new count
// dp[i]: max sum up till i. including i.
int max = nums[0];
int[] dp = new int[nums.length];
Arrays.fill(dp, 0);
dp[0]=nums[0];
for(int i=1; i<nums.length; i++){
int addCurr = dp[i-1] + nums[i];
int dontAdd = nums[i];
if(addCurr > dontAdd){
max = Math.max(addCurr, max);
dp[i]=addCurr;
} else {
dp[i]=dontAdd;
max = Math.max(dontAdd, max);
}
}
return max;
}
}Q2 Given a string, find the length of the longest substring without repeating characters.
Approach 1: Naive brute force where you try every combination of substrings
Approach 2: Optimised brute force. For each starting index i, find the longest substring. O(n)*O(n)=O(n²)
Approach 3:
Can use HashMap
Hard question…i could not figure out how to do the hashmap method as suggested by huahua. Spent a good hour trying and failing…then I copied this solution below from youtube….my brain just isnt working…
currSubstring.substring(1); // Means only keep characters after the first.
// 2023: Most recent attempt
class Solution {
public int lengthOfLongestSubstring(String s) {
// Sliding window
if (s.length()==0) return 0;
HashSet<Character> set = new HashSet<>();
int max = 1;
int start=0;
int end=0;
while(start<=end && end<s.length()){
if(set.contains(s.charAt(end))){
set.remove(s.charAt(start));
start++;
} else {
set.add(s.charAt(end));
max = Math.max(max, set.size());
end++;
}
}
return max;
}
}340. Longest Substring with At Most K Distinct Characters
Given a string, find the length of the longest substring T that contains at most k distinct characters.
Example 1:
Input: s = "eceba", k = 2
Output: 3
Explanation: The substring is "ece" with length 3.Example 2:
Input: s = "aa", k = 1
Output: 2
Explanation: The substring is "aa" with length 2.class Solution {
public int lengthOfLongestSubstringKDistinct(String s, int k) {
HashSet<Character> set = new HashSet<>();
HashMap<Character, Integer> setCount = new HashMap<>();
int max = 1;
int start = 0;
int end = 0;
if (k==0) return 0;
while(start<=end && end<s.length()){
Character curr = s.charAt(end);
set.add(curr);
int cnt = setCount.getOrDefault(curr, 0);
setCount.put(curr, cnt+1);
while(set.size() > k){
// remove
Character charToRemove = s.charAt(start);
if (set.contains(charToRemove)){
int currCount = setCount.get(charToRemove);
if (currCount == 1){
set.remove(charToRemove);
}
setCount.put(charToRemove, currCount-1);
start++;
}
}
max = Math.max(max, end-start+1);
end++;
}
return max;
}
}LEETCODE 1423 Maximum Points You Can Obtain from Cards
There are several cards arranged in a row, and each card has an associated number of points. The points are given in the integer array cardPoints.
In one step, you can take one card from the beginning or from the end of the row. You have to take exactly k cards.
Your score is the sum of the points of the cards you have taken.
Given the integer array cardPoints and the integer k, return the maximum score you can obtain.
Example 1:
Input: cardPoints = [1,2,3,4,5,6,1], k = 3
Output: 12
Explanation: After the first step, your score will always be 1. However, choosing the rightmost card first will maximize your total score. The optimal strategy is to take the three cards on the right, giving a final score of 1 + 6 + 5 = 12.Example 2:
Input: cardPoints = [2,2,2], k = 2
Output: 4
Explanation: Regardless of which two cards you take, your score will always be 4.Example 3:
Input: cardPoints = [9,7,7,9,7,7,9], k = 7
Output: 55
Explanation: You have to take all the cards. Your score is the sum of points of all cards.class Solution {
public int maxScore(int[] cardPoints, int k) {
int[] front = new int[cardPoints.length+1]; // front[i] represents the sum of cards if we take i cards from the start
int[] end = new int[cardPoints.length+1]; // end[i] represents the sum of cards if we take i cards from the end
// index 0 -> Take no card, hence is 0 by default
for(int i=1; i<=cardPoints.length; i++){
front[i] = front[i-1] + cardPoints[i-1];
end[i]=cardPoints[cardPoints.length-i]+end[i-1];
}
int max = 0;
int i=0;
while(i<=k){
max = Math.max(max, front[i] + end[k-i]);
i++;
}
return max;
}
}class Solution {
public:
int maxScore(vector<int>& cardPoints, int k) {
if(k>cardPoints.size()) return 0;
vector<int> left;
int sum = 0;
left.push_back(0);
for(int i=0; i<cardPoints.size(); i++){
sum+=cardPoints[i];
left.push_back(sum);
}
vector<int> right;
right.push_back(0);
sum = 0;
for(int i=cardPoints.size()-1; i>=0; i--){
sum+=cardPoints[i];
right.push_back(sum);
}
int maxScore = 0;
for(int takeLeft=0; takeLeft<=k; takeLeft++){
maxScore = max(maxScore, left[takeLeft]+right[k-takeLeft]);
}
return maxScore;
}
};Two Sum: Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
new int[] {1,2,3,4};
Need to be clear of what values you are storing in the Map.
167. Two Sum II — Input Array Is Sorted
Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.
Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.
The tests are generated such that there is exactly one solution. You may not use the same element twice.
Your solution must use only constant extra space.
Example 1:
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].Example 2:
Input: numbers = [2,3,4], target = 6
Output: [1,3]
Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].Example 3:
Input: numbers = [-1,0], target = -1
Output: [1,2]
Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].Now, we need to make use of the property that it is sorted.
We use two indices, initially pointing to the first and the last element, respectively. Compare the sum of these two elements with target. If the sum is equal to target, we found the exactly only solution. If it is less than target, we increase the smaller index by one. If it is greater than target, we decrease the larger index by one. Move the indices and repeat the comparison until the solution is found.
class Solution {
public int[] twoSum(int[] numbers, int target) {
int start=0;
int end=numbers.length-1;
while(start<end){
int sum = numbers[start] + numbers[end];
if(sum < target){
start++;
} else if (sum > target){
end--;
} else{
return new int[]{start+1, end+1};
}
}
return new int[0];
}
}- Time complexity: O(n). The input array is traversed at most once. Thus the time complexity is O(n).
- Space complexity: O(1). We only use additional space to store two indices and the sum, so the space complexity is O(1).
Leetcode 15 Three Sum: Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:
The solution set must not contain duplicate triplets.
Example:
Given array nums = [-1, 0, 1, 2, -1, -4],A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
Can make use of the two sum II function.
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i < nums.length && nums[i] <= 0; ++i)
if (i == 0 || nums[i - 1] != nums[i]) {
twoSumII(nums, i, res);
}
return res;
}
void twoSumII(int[] nums, int i, List<List<Integer>> res) {
int lo = i + 1, hi = nums.length - 1;
while (lo < hi) {
int sum = nums[i] + nums[lo] + nums[hi];
if (sum < 0) {
++lo;
} else if (sum > 0) {
--hi;
} else {
res.add(Arrays.asList(nums[i], nums[lo++], nums[hi--]));
while (lo < hi && nums[lo] == nums[lo - 1])
++lo;
}
}
}
}My initial solution
This solution does not pass the time-complexity..but i spent very long to come up with it so i shall keep it. It passes 311/313 test cases on leet code.
Leetcode 16 Three sum closest
Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target.
Return the sum of the three integers.
You may assume that each input would have exactly one solution.
Example 1:
Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).Example 2:
Input: nums = [0,0,0], target = 1
Output: 0
Explanation: The sum that is closest to the target is 0. (0 + 0 + 0 = 0).class Solution {
public int threeSumClosest(int[] nums, int target) {
int diff = Integer.MAX_VALUE;
int sz = nums.length;
Arrays.sort(nums);
for (int i = 0; i < sz && diff != 0; ++i) {
int lo = i + 1;
int hi = sz - 1;
while (lo < hi) {
int sum = nums[i] + nums[lo] + nums[hi];
if (Math.abs(target - sum) < Math.abs(diff)) {
diff = target - sum;
}
if (sum < target) {
++lo;
} else {
--hi;
}
}
}
return target - diff;
}
}
259. 3Sum Smaller (Premium)
Given an array of n integers nums and an integer target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.
Example 1:
Input: nums = [-2,0,1,3], target = 2
Output: 2
Explanation: Because there are two triplets which sums are less than 2:
[-2,0,1]
[-2,0,3]Example 2:
Input: nums = [], target = 0
Output: 0Example 3:
Input: nums = [0], target = 0
Output: 0// THIS SOLUTION IS WRONG...it doesn't take all the possible combinations because we never
// update low...
class Solution {
List<List<Integer>> ls;
public int threeSumSmaller(int[] nums, int target) {
ls = new LinkedList<>();
Arrays.sort(nums);
for(int i=0; i<nums.length && nums[i]<target; i++){
if(i==0 || nums[i]!=nums[i-1]){
search(i, target, nums);
}
}
return ls.size();
}
public void search(int i, int target, int[]nums){
int low = i+1;
int high = nums.length-1;
while(low<high){
int sum = nums[i]+nums[low]+nums[high];
if(sum<target){
ls.add(Arrays.asList(i, low, high));
high--;
} else {
high--;
}
}
}
}// Second wrong attempt
class Solution {
public int threeSumSmaller(int[] nums, int target) {
Arrays.sort(nums);
int result = 0;
for(int i=0; i<nums.length && nums[i]<target; i++){
if(i==0 || nums[i]!=nums[i-1]){
int count = search(i, target, nums);
System.out.println(count);
result+=count;
}
}
return result;
}
public int search(int i, int target, int[]nums){
int low = i+1;
int high = nums.length-1;
int rightMost = 0;
while(low<high && high<=nums.length-1){
int sum = nums[i]+nums[low]+nums[high];
if(sum<target){
rightMost = high;
high++;
} else {
high--;
}
}
return high==nums.length? high-low-1 : high-low;
}
}Leetcode soln
class Solution {
public int threeSumSmaller(int[] nums, int target) {
Arrays.sort(nums);
int result = 0;
for(int i=0; i<nums.length-2; i++){
int count = search(nums, i+1, target-nums[i]);
result+=count;
}
return result;
}
public int search(int[] nums, int startIndex, int target){
int sum = 0;
for(int i=startIndex; i<nums.length; i++){
int largestEndIndex = binarySearch(nums, i, target-nums[i]);
sum+=largestEndIndex-i;
}
return sum;
}
// By the time we run this method, we would have already deducted 2 numbers from target.
public int binarySearch(int[] nums, int startIndex, int target){
int left = startIndex;
int right = nums.length-1;
int best = startIndex;
while(left<=right){
int mid = left + (right-left)/2;
if(nums[mid] < target){
best = mid;
left=mid + 1; // See if can go higher...
} else {
right=mid-1;
}
}
return best;
}
}
Longest Common subsequence Leetcode 1143
Given two strings text1 and text2, return the length of their longest common subsequence.
A subsequence of a string is a new string generated from the original string with some characters(can be none) deleted without changing the relative order of the remaining characters. (eg, “ace” is a subsequence of “abcde” while “aec” is not). A common subsequence of two strings is a subsequence that is common to both strings.
If there is no common subsequence, return 0.
Example 1:
Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: The longest common subsequence is "ace" and its length is 3.Example 2:
Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.Example 3:
Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.
The idea is to have 2D matrix where each index dp[i][j] represents the longest substring of the two strings: string1[0…..i] and string2[0…..j].
If you need to print out the string:
Cracking the coding interview
(1) Is Unique: Implement an algorithm to determine if a string has all unique characters. Cannot use additional data structures?
Approach 1: Brute Force 2 For Loop
Approach 2: Sorting O(nlogn)
Approach 3: Use of extra data structures O(n) -> Can use HashMap
Approach 4: Without extra data structure
(2) Does string2 contains permutation of string1? (Leet code)
found this hard...spent 2 hours and in the end just gave up by looking at the solution.
Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string’s permutations is the substring of the second string.
Example 1:
Input: s1 = "ab" s2 = "eidbaooo"
Output: True
Explanation: s2 contains one permutation of s1 ("ba").Example 2:
Input: s1= "ab" s2 = "eidboaoo"
Output: False
- Use sliding window approach here. The size of the window is length of string 1.
- Each time we iterate through String 2, we check if the count of characters for both are the same.
- Before line 11 is reached, the s1map and s2map will contain the mapping of the characters in both string 1 and a subset of string 2. Substring of length string 1 of string 2.
- Then we will have 2 maps called s1map and s2map.
- Afterwards, we immediately check whether they have the same values via matches function.
- Then, if it doesn’t match, we will go on to change the map of S2 by checking the next character of string2. For eg, if string1 is of length X and string2 is of length Y, then the next char to be explored will be at position (Y-X-1). This is line 14.
- In line 15, we will attempt to remove the first character of string2 at position 0.
- So everytime we check for similarity in the match function, we are keeping the size of the window to the length of string 1.
class Solution {
public boolean checkInclusion(String s1, String s2) {
HashMap<Character, Integer> s1Map = new HashMap<>();
HashMap<Character, Integer> s2Map = new HashMap<>();
if (s2.length() < s1.length()) return false;
for(int i=0; i<s1.length(); i++){
int count = s1Map.getOrDefault(s1.charAt(i), 0);
s1Map.put(s1.charAt(i), count+1);
int count3 = s2Map.getOrDefault(s2.charAt(i), 0);
s2Map.put(s2.charAt(i), count3+1);
}
for(int i=0; i<=s2.length()-s1.length(); i++){
String subStringOfS2 = s2.substring(i, i+s1.length());
// Remove prev
if (i>0){
int count2 = s2Map.getOrDefault(s2.charAt(i-1), 0);
if(count2 -1 == 0){
s2Map.remove(s2.charAt(i-1));
} else {
s2Map.put(s2.charAt(i-1), count2-1);
}
}
if (i>0){
// Add new
int count = s2Map.getOrDefault(subStringOfS2.charAt(subStringOfS2.length()-1), 0);
s2Map.put(subStringOfS2.charAt(subStringOfS2.length()-1), count+1);
}
if(compareHashMap(s1Map, s2Map)){
return true;
}
// compare hashmap of s1 and s2..if match just return true
}
return false;
}
public boolean compareHashMap(HashMap<Character, Integer> s1Map, HashMap<Character, Integer> s2Map){
for(Map.Entry<Character, Integer> entry: s1Map.entrySet()){
Character cc = entry.getKey();
int count = entry.getValue();
if(!s2Map.containsKey(cc)){
return false;
}
int s2Count = s2Map.get(cc);
if(s2Count!=count){
return false;
}
}
return true;
}
}(3) Leet Code 49 Group Anagrams
Given an array of strings, group anagrams together.
Example:
Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]First things to think of -> Use of Hash map
One correct solution is to set the key of the HashMap to be the sorted string of each anagram. For eg, if we have “cat”, “tac”, “cta”, the key of this group would be “act” which is the sorted version of those strings.
char[] ca = eachString.toCharArray(); //Convert to array of characters
Arrays.sort(ca) //Sort it;
String key = String.valueOf(ca); //Convert back to string format
Note that when we want to do integer, we do Integer.parseInt();
(5) Leet Code 48 Rotate Image (Matrix)
You are given an n x n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).
Note:
You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.
Example 1:
Given input matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],rotate the input matrix in-place such that it becomes:
[
[7,4,1],
[8,5,2],
[9,6,3]
]
Example 2:
Given input matrix =
[
[ 5, 1, 9,11],
[ 2, 4, 8,10],
[13, 3, 6, 7],
[15,14,12,16]
], rotate the input matrix in-place such that it becomes:
[
[15,13, 2, 5],
[14, 3, 4, 1],
[12, 6, 8, 9],
[16, 7,10,11]
]
//Another attempt in 2023
class Solution {
public void rotate(int[][] matrix) {
int[] lines = new int[matrix.length*matrix[0].length];
int count = 0;
for(int row=0; row<matrix.length; row++){
for(int col=0; col<matrix[0].length; col++){
lines[count]=matrix[row][col];
count++;
}
}
int count2=0;
for(int col=matrix[0].length-1; col>=0; col--){
for(int row=0; row<matrix.length; row++){
matrix[row][col]=lines[count2];
count2++;
}
}
}
}Leetcode solution
class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
for (int i = 0; i < (n + 1) / 2; i ++) {
for (int j = 0; j < n / 2; j++) {
int temp = matrix[n - 1 - j][i];
matrix[n - 1 - j][i] = matrix[n - 1 - i][n - j - 1];
matrix[n - 1 - i][n - j - 1] = matrix[j][n - 1 -i];
matrix[j][n - 1 - i] = matrix[i][j];
matrix[i][j] = temp;
}
}
}
}
public void rotate(int[][] matrix){
transpose(matrix);
reflect(matrix);
}
public void transpose(int[][] matrix){
int n = matrix.length;
for(int i=0; i<n; i++){
for(int j=i+1; j<n; j++){
int tmp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = tmp;
}
}
}
public void reflect(int[][] matrix){
int n = matrix.length;
int m = matrix[0].length;
for(int i=0; i<n; i++){
for(int j=0; j<m/2; j++){
int temp = matrix[i][j];
matrix[i][j] = matrix[i][n-j-1];
matrix[i][n-j-1] = temp;
}
}
}(6) Leet Code 274 H-Index
Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher’s h-index.
According to the definition of h-index on Wikipedia: “A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each.”
Example:
Input: citations = [3,0,6,1,5]
Output: 3
Explanation: [3,0,6,1,5] means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, her h-index is 3.Note: If there are several possible values for h, the maximum one is taken as the h-index.
class Solution {
public int hIndex(int[] citations) {
Arrays.sort(citations); //ascending
for(int i=citations.length-1; i>=0; i--){
int elmOnRight = citations.length-1-i;
if(elmOnRight >= citations[i]){
return elmOnRight;
}
}
return citations.length;
}
}If the number of citation papers we have seen (excluding the current one) is bigger or equal to the current h value, then return the number of citation papers seen.
See X papers, all must be at least h value — current. Compare number of X paper with h value. We want number of papers X to be ≥ h.
Leetcode answer (This is harder to understand, i prefer the one above)
Approach #1 (Sorting)
Intuition
Think geometrically. Imagine plotting a histogram where the y-axis represents the number of citations for each paper. After sorting in descending order, h-index is the length of the largest square in the histogram.
public class Solution {
public int hIndex(int[] citations) {
// sorting the citations in ascending order
Arrays.sort(citations);
// finding h-index by linear search
int i = 0;
while (i < citations.length && citations[citations.length - 1 - i] > i) {
i++;
}
return i; // after the while loop, i = i' + 1
}
}275. H-Index II
Given an array of integers citations where citations[i] is the number of citations a researcher received for their ith paper and citations is sorted in ascending order, return the researcher's h-index.
According to the definition of h-index on Wikipedia: The h-index is defined as the maximum value of h such that the given researcher has published at least h papers that have each been cited at least h times.
You must write an algorithm that runs in logarithmic time.
Example 1:
Input: citations = [0,1,3,5,6]
Output: 3
Explanation: [0,1,3,5,6] means the researcher has 5 papers in total and each of them had received 0, 1, 3, 5, 6 citations respectively.
Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, their h-index is 3.Example 2:
Input: citations = [1,2,100]
Output: 2class Solution {
public:
int hIndex(vector<int>& citations) {
int low = 0;
int high = citations.size()-1;
int best = -1;
int size = citations.size();
// We need to find the rightmost 'index' such that: (citations[index] <= n - index)
while(low<=high){
int mid = low + (high-low) / 2;
if(checkValid(citations, mid)){
best = max(citations[mid], best);
low = mid + 1; // can go higher?
} else {
best = max(best, size-mid); // the best number could be num of elements to the right of mid index
// eg, [0,0,4,4] -> best: 2
high = mid - 1; // need to go lower..
}
}
return best;
}
bool checkValid(vector<int>& citations, int index){
int val = citations[index];
int rightElementCount = citations.size()-index;
return rightElementCount >= val;
}
};The fact that the algo must be in log time hints that we should use binary search.
7) Leet Code 150. Evaluate Reverse Polish Notation
Reverse polish notation -> Postfix notation in which operators follow their operands.
Polish notation -> Operators precede their operands.
The reverse Polish scheme was proposed in 1954 by Arthur Burks, Don Warren, and Jesse Wright[4] and was independently reinvented by Friedrich L. Bauer and Edsger W. Dijkstra in the early 1960s to reduce computer memory access and utilize the stack to evaluate expressions
Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +, -, *, /. Each operand may be an integer or another expression.
Note:
- Division between two integers should truncate toward zero.
- The given RPN expression is always valid. That means the expression would always evaluate to a result and there won’t be any divide by zero operation.
Example 1:
Input: ["2", "1", "+", "3", "*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9Example 2:
Input: ["4", "13", "5", "/", "+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6When the current element is not a number, we will pop out 2 elements from the stack and perform the operation. When the current element is a number, we just append it to the stack.
class Solution {
public int evalRPN(String[] tokens) {
Stack<String> st = new Stack<>();
for(int i=0; i<tokens.length; i++){
String tok = tokens[i];
if(tok.equals("+")){
String first = st.pop();
String second = st.pop();
String res = String.valueOf(Integer.parseInt(first) + Integer.parseInt(second));
st.push(res);
} else if (tok.equals("-")){
String first = st.pop();
String second = st.pop();
String res = String.valueOf(Integer.parseInt(second) - Integer.parseInt(first));
st.push(res);
} else if (tok.equals("*")){
String first = st.pop();
String second = st.pop();
String res = String.valueOf(Integer.parseInt(second) * Integer.parseInt(first));
st.push(res);
} else if (tok.equals("/")){
String first = st.pop();
String second = st.pop();
String res = String.valueOf(Integer.parseInt(second) / Integer.parseInt(first));
st.push(res);
} else {
// number
st.add(tok);
}
}
return Integer.parseInt(st.pop());
}Not the neatest code but it works.
class Solution {
public:
unordered_map<string, function<int(int, int)>> opMap {
{"+", [](int a, int b) { return a + b; }},
{"-", [](int a, int b) { return a - b; }},
{"*", [](int a, int b) { return a * b; }},
{"/", [](int a, int b) { return floor(a / b); }},
};
int evalRPN(vector<string>& tokens) {
stack<int> s {};
int a, b;
int res = 0;
for (string& token : tokens) {
if (opMap.find(token) == opMap.end()) {
s.push(stoi(token));
continue;
}
a = s.top(); // read element
s.pop(); // remove element
b = s.top();
s.pop();
s.push(opMap[token](b, a)); // evaluate
}
return s.top();
}
};8) Leet Code 14 Longest Common Prefix
Write a function to find the longest common prefix string among an array of strings.
If there is no common prefix, return an empty string "".
Example 1:
Input: ["flower","flow","flight"]
Output: "fl"Example 2:
Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.class Solution {
public String longestCommonPrefix(String[] strs) {
String prefix = strs[0];
for(int i=1; i<strs.length; i++){
String curr = strs[i];
while(!curr.startsWith(prefix) && prefix!=""){
prefix=prefix.substring(0, prefix.length()-1); // remove last char
}
}
return prefix;
}
}
// in c++, to get startsWith, we use the find() method where, str.find(prefix) == 0- Set prefix to be the first string in the strs array
- As we iterate through the other elements of the string array, we make the prefix smaller and smaller if it does not exist in the first few parts of the string. We remove the last character.
9) Leetcode 179 form the largest number
Given a list of non negative integers, arrange them such that they form the largest number.
Example 1:
Input: [10,2]
Output: "210"
Using comparator:
It returns a positive value if obj1 is greater than obj2. Otherwise, a negative value is returned. By overriding compare( ), you can alter the way that objects are ordered.
- NumComparator will arrange a in front of b => (a,b) if we return a positive value.
- If we want b to be arranged in front of a => (b,a) We need a negative value to be returned. When do we want this arrangement, (b,a)? When (b+a) > (a+b).
- String compareTo: If first string is lexicographically greater than second string, it returns positive number.
- Hence, we want to make sure that we compare (b+a).compareTo(a+b) which corresponds to the code above.
- order2.compareTo( order1); Returns negative when order1 is smaller. Hence, when order1 is smaller, it means a+b < b+a. This means we dont want a to be put in front of b and we can directly return.
- Note that in the comparator, we don’t convert the order1 and order2 into Integers and compare their numerical value. This is because we don’t want to have integer overflow.
class Solution {
public:
string largestNumber(vector<int>& nums) {
if(nums.size() == 0) return "0";
std::sort(nums.begin(), nums.end(), [](int num1, int num2){
string string1 = to_string(num1) + to_string(num2);
string string2 = to_string(num2) + to_string(num1);
return string1 > string2;
// The comparator function should return true if the element a should be placed before the element b in the sorted order, and false otherwise.
});
int first = nums[0];
if(first==0) {
cout << "ll" << endl;
string hi("0");
return hi;
}
cout<<"Pass"<<endl;
string result = "";
for(int n: nums){
result += to_string(n);
}
return result;
}
};10. ZigZag Conversion
The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
P A H N
A P L S I I G
Y I RAnd then read line by line: "PAHNAPLSIIGYIR"
Write the code that will take a string and make this conversion given a number of rows:
string convert(string s, int numRows);Example 1:
Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"Example 2:
Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:P I N
A L S I G
Y A H R
P I
- Create an index that iterate from row 0…numRows, then back to 0 and repeat.
class Solution {
public String convert(String s, int numRows) {
if (numRows==1) return s;
LinkedList<Character> [] res = new LinkedList[numRows];
for(int i=0; i<numRows; i++){
res[i] = new LinkedList<Character>();
}
int row=0;
boolean directionGoDown = true;
for(int i=0; i<s.length(); i++){
char c = s.charAt(i);
res[row].add(c);
if (row==numRows-1){
row=row-1;
directionGoDown = false;
} else if (row == 0){
row=row+1;
directionGoDown = true;
} else if (directionGoDown){
row++;
} else if (!directionGoDown){
row--;
}
}
String resultString = "";
for(int i=0; i<numRows; i++){
LinkedList<Character> currRow = res[i];
for(Character c: currRow){
resultString+=c;
}
}
return resultString;
}
}Leetcode 281 Zigzag iterator
Given two vectors of integers v1 and v2, implement an iterator to return their elements alternately.
Implement the ZigzagIterator class:
ZigzagIterator(List<int> v1, List<int> v2)initializes the object with the two vectorsv1andv2.boolean hasNext()returnstrueif the iterator still has elements, andfalseotherwise.int next()returns the current element of the iterator and moves the iterator to the next element.
Example 1:
Input: v1 = [1,2], v2 = [3,4,5,6]
Output: [1,3,2,4,5,6]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,3,2,4,5,6].Example 2:
Input: v1 = [1], v2 = []
Output: [1]Example 3:
Input: v1 = [], v2 = [1]
Output: [1]public class ZigzagIterator {
private List<List<Integer>> vectors = new ArrayList<>();
private LinkedList<Pair<Integer, Integer>> queue = new LinkedList<>();
public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
this.vectors.add(v1);
this.vectors.add(v2);
int index=0;
for(List<Integer> vec: vectors){
if(vec.size()>0){
this.queue.add(new Pair<Integer, Integer> (index, 0));
}
index++;
}
}
public int next() {
Pair<Integer, Integer> pointer = this.queue.removeFirst();
Integer vecIndex = pointer.getKey();
Integer elemIndex = pointer.getValue();
Integer nextElemIndex = elemIndex+1;
if(nextElemIndex < this.vectors.get(vecIndex).size()){
this.queue.addLast(new Pair<>(vecIndex, nextElemIndex));
}
return this.vectors.get(vecIndex).get(elemIndex);
}
public boolean hasNext() {
this.queue.size()>0;
}
}
/**
* Your ZigzagIterator object will be instantiated and called as such:
* ZigzagIterator i = new ZigzagIterator(v1, v2);
* while (i.hasNext()) v[f()] = i.next();
*/
11. Leetcode 916 Word Subsets
We are given two arrays A and B of words. Each word is a string of lowercase letters.
Now, say that word b is a subset of word a if every letter in b occurs in a, including multiplicity. For example, "wrr" is a subset of "warrior", but is not a subset of "world".
Now say a word a from A is universal if for every b in B, b is a subset of a.
Return a list of all universal words in A. You can return the words in any order.
Example 1:
Input: A = ["amazon","apple","facebook","google","leetcode"], B = ["e","o"]
Output: ["facebook","google","leetcode"]
class Solution {
public List<String> wordSubsets(String[] words1, String[] words2) {
int[] count = new int[26];
int[] tmp;
for(String word: words2){
tmp = counter(word);
for(int j=0; j<26; j++){
count[j] = Math.max(count[j], tmp[j]); // why do we need this?? SO that we add on to the count of the previous word in words2
}
}
// At this point, count will contain all the counts of words2
List<String> res = new ArrayList<>();
for(String wordSingle: words1){
tmp = counter(wordSingle);
int i=0;
for(i=0; i<26; ++i){
// every word in words2 has to be found in
// words1.
// Whatever that is in words1 has to be <= words2
if(tmp[i] < count[i]) break;
}
if(i==26) res.add(wordSingle);
}
return res;
}
int[] counter(String word){
int[]count = new int[26];
for(char c: word.toCharArray()){
count[c-'a']++;
}
return count;
}
}Below is my original attempt, that is wrong…i think i misunderstood the question.
class Solution {
public List<String> wordSubsets(String[] words1, String[] words2) {
Map<String, Integer> map2 = new HashMap<>();
for(String s: words2){
int count = map2.getOrDefault(s, 0);
map2.put(s, count+1);
} // I think why this code doesnt work is because if s is made up of
// more than 1 chars, then we don't want it to be in the hashmap as
// for example, "ab". We want to separate them and store "a" and "b"
System.out.println(map2);
List<String> result = new LinkedList<>();
for(String word: words1){
boolean toAdd = true;
for(Map.Entry<String, Integer> entry: map2.entrySet()){
int count = countSubstring(word, entry.getKey());
if (count < entry.getValue()){
toAdd = false;
}
}
if(toAdd){
result.add(word);
}
}
return result;
}
public static int countSubstring(String str, String subStr) {
int count = 0;
int index = 0;
while ((index = str.indexOf(subStr, index)) != -1) {
count++;
index += subStr.length();
}
return count;
}
}
12 Leetcode 376 Wriggle Subsequence
A sequence of numbers is called a wiggle sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a wiggle sequence.
For example, [1,7,4,9,2,5] is a wiggle sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, [1,4,7,2,5] and [1,7,4,5,5] are not wiggle sequences, the first because its first two differences are positive and the second because its last difference is zero.
Given a sequence of integers, return the length of the longest subsequence that is a wiggle sequence. A subsequence is obtained by deleting some number of elements (eventually, also zero) from the original sequence, leaving the remaining elements in their original order.
// wrong and completed attempt
public int wiggleMaxLength(int[] nums) {
if (nums.length <= 2) return nums.length;
int max = 1;
Info[] dp = new Info[nums.length];
dp[0] = new Info(1, false, true);
if (nums[1] == nums[0]){
dp[1] = new Info(1, false, true);
} else if (nums[1] > nums[0]){
dp[1] = new Info(2, true);
} else {
dp[1] = new Info(2, false);
}
max = Math.max(max, dp[1].length);
for(int i=2; i<nums.length; i++){
int currNum = nums[i];
Info curr = new Info(2, false);
for(int j=i-1; j>=0; j--){
Info prev = dp[j];
int prevNum = nums[j];
if((prev.restart || prev.nextShouldBeNegative) && currNum < prevNum){
curr.length = Math.max(1 + prev.length, curr.length);
curr.nextShouldBeNegative = false;
curr.restart = false;
dp[i] = curr;
} else if ((prev.restart || !prev.nextShouldBeNegative) && currNum > prevNum){
curr.length = Math.max(1 + prev.length, curr.length);
curr.nextShouldBeNegative = true;
curr.restart = false;
dp[i] = curr;
} else {
curr.restart = true;
curr.
}
}
dp[i] = curr;
System.out.print(i);
System.out.print(" ");
System.out.print(dp[i].length);
System.out.println(dp[i].nextShouldBeNegative);
max = Math.max(max, dp[i].length);
}
return max;
}
public static class Info{
private int length;
private boolean nextShouldBeNegative;
private boolean restart;
public Info(int length, boolean nextShouldBeNegative){
this.length = length;
this.nextShouldBeNegative = nextShouldBeNegative;
this.restart = false;
}
public Info(int length, boolean nextShouldBeNegative, boolean restart){
this.length = length;
this.nextShouldBeNegative = nextShouldBeNegative;
this.restart = restart;
}
}13 Leetcode 324 Wiggle Sort II
Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]....
Example 1:
Input: nums = [1, 5, 1, 1, 6, 4]
Output: One possible answer is [1, 4, 1, 5, 1, 6].Example 2:
Input: nums = [1, 3, 2, 2, 3, 1]
Output: One possible answer is [2, 3, 1, 3, 1, 2].Solution #1
A pretty simple and straightforward solution is:
- Sort the array (with an auxiliary array)
- Copy the elements to the correct positions
It’s the code:
class Solution {
public void wiggleSort(int[] nums) {
int[] val = Arrays.copyOf(nums, nums.length);
Arrays.sort(val);
int idx = val.length - 1;
for(int i = 1;i < nums.length;i += 2) nums[i] = val[idx--];
for(int i = 0;i < nums.length;i += 2) nums[i] = val[idx--];
}
}Note that we don’t need to calculate all the concrete positions to be copied; we just need to go through the array by odd and even positions till exhausting the array.
The space complexity is O(N), and the time complexity is O(NlogN) + O(N) (sorting + filling) = O(NlogN).
Solution #2
To achieve space complexity O(1) and time complexity O(N), a popular approach is:
The idea is based on the fact that if we make sure that all even positioned (at index 0, 2, 4, ..) elements are greater than their adjacent odd elements.
We traverse an array once, visiting all even positions. Then, make sure that the numbers at even positions are greater than its left and right elements. If it is not bigger, then we swap them.
Leetcode 239: Sliding Window Maximum
You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.
Return the max sliding window.
Example 1:
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation:
Window position Max
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7Example 2:
Input: nums = [1], k = 1
Output: [1] public int[] maxSlidingWindow(int[] nums, int k) {
List<Integer> output = new ArrayList<>();
Deque<Integer> q = new LinkedList<>();
int l = 0, r = 0;
while(r < nums.length) {
// pop smaller values from q
while(!q.isEmpty() && nums[q.peekLast()] < nums[r]) {
q.pollLast();
}
q.offer(r);
// Remove value in the queue that is outside of the curr window
// range (The one right before)
if (l > q.peek()) {
// q.peek() check head..if the left index is more than the index of the value in queue
q.poll(); // remove head
}
// store the rightmost value in the output.
if ((r + 1) >= k) {
output.add(nums[q.peek()]);
l++;
}
r++;
}
int[] result = new int[nums.length-k+1];
for(int j=0; j<output.size(); j++){
result[j] = output.get(j);
}
return result;
}We maintain a deque (double-ended queue) to keep track of the maximum value in the current sliding window. We iterate through the input array nums and maintain the deque such that it is a monotonically decreasing queue.
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int[] result = new int[nums.length-k+1];
Deque<Integer> q = new LinkedList<>();
int r=0;
for(int i=0; i<nums.length; i++){
while(q.size()>0 && nums[i] > nums[q.peekLast()]){
q.removeLast(); // remove values smaller than nums[i]
}
q.addLast(i);
if(q.peekFirst()<i-k+1){
q.removeFirst(); // remove index out of range
}
if(i>=k-1){
result[r++]=nums[q.peekFirst()];
}
}
return result;
}
}If we have a window, and we see a value that is greater than values before it, we can ignore all the values before it. Remove them from our window since that value will definitely be the maximum as long as it is within our current window range.
An example to consider:
[8,7,6,9], k =2
[8], i=0
[8,7], i=1, result=[8]
[7,6], i=2, result=[8,7]
[9], i=3, result[8,7,9]The max value will always be at the head of the queue.
At each iteration,
Then, we always add current value into the queue.
The queue is monotonically decreasing.
The algorithm is:
1. always pop from head of queue to remove out of range values
2. check current value against queue’s items from back to front. We will pop a value from the back of the queue if the value in queue is smaller than the current val. Since we know current val will be the max for current range.
3. add current value to queue.
4. get max value from the head of the queue. Add to result.
Note that our queue stores index so that we can check for out of range easily.
The solution given by leetcode is hard to understand, so i wont copy it here.
329. Longest Increasing Path in a Matrix
Given an m x n integers matrix, return the length of the longest increasing path in matrix.
From each cell, you can either move in four directions: left, right, up, or down. You may not move diagonally or move outside the boundary (i.e., wrap-around is not allowed).
Example 1:
Input: matrix = [[9,9,4],[6,6,8],[2,1,1]]
Output: 4
Explanation: The longest increasing path is [1, 2, 6, 9].Example 2:
Input: matrix = [[3,4,5],[3,2,6],[2,2,1]]
Output: 4
Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.Example 3:
Input: matrix = [[1]]
Output: 1class Solution {
int[][] cache;
public int longestIncreasingPath(int[][] matrix) {
cache = new int[matrix.length][matrix[0].length];
int longest = 0;
for(int i=0; i<matrix.length; i++){
for(int j=0; j<matrix[0].length; j++){
int len = traverse(matrix, i, j, -1);
longest = Math.max(len, longest);
}
}
return longest;
}
public int traverse(int[][] matrix, int i, int j, int prev){
if(i<0 || j<0 || i>=matrix.length || j>=matrix[0].length){
return 0;
}
if(matrix[i][j]<=prev){
return cache[i][j]=0;
}
if(cache[i][j] != 0){
return cache[i][j];
}
int left = traverse(matrix, i, j-1, matrix[i][j]);
int right = traverse(matrix, i, j+1, matrix[i][j]);
int up = traverse(matrix, i-1, j, matrix[i][j]);
int down = traverse(matrix, i+1, j, matrix[i][j]);
return cache[i][j] = Math.max(left, Math.max(right, Math.max(up, down))) + 1;
}
}Leetcode 688 Knight probability in chessboard
class Solution {
public double knightProbability(int n, int k, int row, int column) {
double[][]dp = new double[n][n];
int[] dr = new int[]{2, 2, 1, 1, -1, -1, -2, -2};
int[] dc = new int[]{1, -2, 2, -2, 2, -2, 1, -1};
dp[row][column]=1;
for(int steps=k; steps>0; steps--){
double[][]dp2 = new double[n][n];
for(int rr=0; rr<n; rr++){
for(int cc=0; cc<n; cc++){
for(int step=0; step<8; step++){
int newRow = rr + dr[step];
int newCol = cc + dc[step];
if (0 <= newRow && newRow < n && 0 <= newCol && newCol < n){
dp2[newRow][newCol] += dp[rr][cc] / 8.0;
}
}
}
}
dp = dp2;
}
double ans = 0.0;
for (double[] r: dp) {
for (double x: r) ans += x;
}
return ans;
}
}i don’t even know what this question is asking…gonna ignore it and hope it doesn’t come up in my interviews.
Leet code 966 Vowel Spellchecker
Given a wordlist, we want to implement a spellchecker that converts a query word into a correct word.
For a given query word, the spell checker handles two categories of spelling mistakes:
Capitalization: If the query matches a word in the wordlist (case-insensitive), then the query word is returned with the same case as the case in the wordlist.
- Example:
wordlist = ["yellow"],query = "YellOw":correct = "yellow" - Example:
wordlist = ["Yellow"],query = "yellow":correct = "Yellow" - Example:
wordlist = ["yellow"],query = "yellow":correct = "yellow"
Vowel Errors: If after replacing the vowels (‘a’, ‘e’, ‘i’, ‘o’, ‘u’) of the query word with any vowel individually, it matches a word in the wordlist (case-insensitive), then the query word is returned with the same case as the match in the wordlist.
- Example:
wordlist = ["YellOw"],query = "yollow":correct = "YellOw" - Example:
wordlist = ["YellOw"],query = "yeellow":correct = ""(no match) - Example:
wordlist = ["YellOw"],query = "yllw":correct = ""(no match)
In addition, the spell checker operates under the following precedence rules:
- When the query exactly matches a word in the wordlist (case-sensitive), you should return the same word back.
- When the query matches a word up to capitalization, you should return the first such match in the wordlist.
- When the query matches a word up to vowel errors, you should return the first such match in the wordlist.
- If the query has no matches in the wordlist, you should return the empty string.
Given some queries, return a list of words answer, where answer[i] is the correct word for query = queries[i].
Note that all cases are exclusive….Need to be clear of the question.
Why do we use putIfAbsent? Why not use the two code of lines below?
wordSetLowerCase.put(lower, word);
deVowel.put(devowel, word);
In the example above, the bottom 2 are the ones we want (for the two sets).
Ans: If we have 2 similar words, we want to use the one that comes first.
For C++
string str = “Hello World”;
// convert to lowercase
std::transform(str.begin(), str.end(), str.begin(), [](unsigned char c){
return std::tolower(c);
});
// replace vowels with ‘#’
std::replace_if(str.begin(), str.end(), [](unsigned char c){
return std::string(“aeiou”).find(std::tolower(c)) != std::string::npos;
}, “#”);
// npos is used to represent char/substring is not found in a string.
Leet Code 1024 Video Stitching
You are given a series of video clips from a sporting event that lasted T seconds. These video clips can be overlapping with each other and have varied lengths.
Each video clip clips[i] is an interval: it starts at time clips[i][0] and ends at time clips[i][1]. We can cut these clips into segments freely: for example, a clip [0, 7] can be cut into segments [0, 1] + [1, 3] + [3, 7].
Return the minimum number of clips needed so that we can cut the clips into segments that cover the entire sporting event ([0, T]). If the task is impossible, return -1.
Example 1:
Input: clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], T = 10
Output: 3
Explanation:
We take the clips [0,2], [8,10], [1,9]; a total of 3 clips.
Then, we can reconstruct the sporting event as follows:
We cut [1,9] into segments [1,2] + [2,8] + [8,9].
Now we have segments [0,2] + [2,8] + [8,10] which cover the sporting event [0, 10].Example 2:
Input: clips = [[0,1],[1,2]], T = 5
Output: -1
Explanation:
We can't cover [0,5] with only [0,1] and [1,2].Example 3:
Input: clips = [[0,1],[6,8],[0,2],[5,6],[0,4],[0,3],[6,7],[1,3],[4,7],[1,4],[2,5],[2,6],[3,4],[4,5],[5,7],[6,9]], T = 9
Output: 3
Explanation:
We can take clips [0,4], [4,7], and [6,9].Example 4:
Input: clips = [[0,4],[2,8]], T = 5
Output: 2
Explanation:
Notice you can have extra video after the event ends.
Note that sorting in Java and C++ is different. In the above, we get ascending order. In C++, the natural order is descending.
Eg, if we have a priority queue, the following will lead to descending order.
auto compare = [](const MyStruct& a, const MyStruct& b) {
return a.value - b.value; // if put a in front of b, return positive value. Will be ordered in descending.
};
std::priority_queue<MyStruct, std::vector<MyStruct>, decltype(compare)> pq(compare);Leet code 215. Kth Largest Element in an Array
Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
Example 1:
Input: [3,2,1,5,6,4] and k = 2
Output: 5Example 2:
Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4The hard part about this question is that we have to do it in O(n) time instead of O(NlogN).
The idea: Quick Select algorithm
The condition at the WHILE loop has to be while left ≤ right. If we remove equality, then we miss the below case where we only have 1 element …
class Solution {
public int findKthLargest(int[] nums, int k) {
return quickSelect(nums, nums.length-k);
}
public int quickSelect(int[] nums, int k){
int low=0;
int right=nums.length-1;
while(low<=right){
// low is the first elem...pivot
int newPivotIndex = low;
for(int i=low+1; i<=right; i++){
if(nums[i]<nums[low]){// compare current val with pivot value...
newPivotIndex++;
swap(nums, newPivotIndex, i);
}
}
swap(nums, newPivotIndex, low);
if(newPivotIndex<k){
low=newPivotIndex+1;
} else if (newPivotIndex>k){
right=newPivotIndex-1;
} else{
return nums[newPivotIndex];
}
}
return -1;
}
public static void swap(int[] nums, int i, int j){
int temp = nums[i];
nums[i]=nums[j];
nums[j]=temp;
}
}Another Solution is to use Heap.
Leetcode 973. K Closest Points to Origin
We have a list of points on the plane. Find the K closest points to the origin (0, 0).
(Here, the distance between two points on a plane is the Euclidean distance.)
You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in.)
Example 1:
Input: points = [[1,3],[-2,2]], K = 1
Output: [[-2,2]]
Explanation:
The distance between (1, 3) and the origin is sqrt(10).
The distance between (-2, 2) and the origin is sqrt(8).
Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.
We only want the closest K = 1 points from the origin, so the answer is just [[-2,2]].Example 2:
Input: points = [[3,3],[5,-1],[-2,4]], K = 2
Output: [[3,3],[-2,4]]
(The answer [[-2,4],[3,3]] would also be accepted.)Leet Code Solution:
class Solution {
public:
vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
quickSelect(points, 0, points.size() - 1, k);
return vector<vector<int>>(points.begin(), points.begin() + k);
}
void quickSelect(vector<vector<int>>& points, int start, int end, int k) {
if (start >= end) return;
int partitionIndex = partition(points, start, end);
if(partitionIndex==k-1){
return;
} else if (partitionIndex>k-1){
quickSelect(points, start, partitionIndex-1, k);
} else {
quickSelect(points, partitionIndex+1, end, k);
}
}
int partition(vector<vector<int>>& points, int start, int end) {
int pivotIndex = start;
double pivotVal = computeDistance(points[start][0], points[start][1]);
for (int i = start + 1; i <= end; i++) {
if (computeDistance(points[i][0], points[i][1]) < pivotVal) {
swap(points[i], points[++pivotIndex]);
}
}
swap(points[start], points[pivotIndex]);
return pivotIndex;
}
double computeDistance(int x, int y) {
return sqrt(x * x + y * y);
}
};
!!!! NEED TO USE DOUBLE otherwise sqrt will cause precision issues.347. Top K Frequent Elements
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
Example 1:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]Example 2:
Input: nums = [1], k = 1
Output: [1]class Solution {
HashMap<Integer, Integer> valueToCount; // num to freq
int[] unique; // contains all unique nums
public int[] topKFrequent(int[] nums, int k) {
valueToCount = new HashMap<>();
for(int i=0; i<nums.length; i++){
int count = valueToCount.getOrDefault(nums[i], 0);
valueToCount.put(nums[i], count+1);
}
int n = valueToCount.size();
unique = new int[n];
int i=0;
for(int num: valueToCount.keySet()){
unique[i]=num;
i++;
}
// kth top element is (n-k)th less frequent.
// elements on left are less freq than right
quickSelect(0, n-1, n-k); // do quick select on freq
// Select top k freq elements
return Arrays.copyOfRange(unique, n - k, n);
}
public void quickSelect(int left, int right, int kSmallest){
if(left == right) return;
int pivotIndex = partition(left, right);
if(pivotIndex == kSmallest) return;
else if (pivotIndex > kSmallest){
quickSelect(left, pivotIndex-1, kSmallest);
} else {
quickSelect(pivotIndex+1, right, kSmallest);
}
}
/*
* Here, left and right represent the indices of the leftmost and rightmost elements of the subarray being sorted.
pivotValue represents the value of the pivot element, and pivotIndex represents the index of the last element that is smaller
than the pivot element.
The loop iterates over each element in the subarray, moving smaller elements to the left of pivotIndex. Once the loop is complete,
the pivot element is swapped with the element at pivotIndex, which places it in its final position in the sorted array.
Finally, pivotIndex is returned as the index of the pivot element in the sorted array.
*/
public int partition(int left, int right){
/*
* it generates a random integer between left and right, inclusive. Here, we first compute the length of the subarray
as (right - left + 1). We then multiply this length by a random number between 0 and 1 using Math.random(), which gives
us a random number between 0 and the length of the subarray. Finally, we add left to this random number to get a random
index between left and right
*/
int randomIndex = left + (int)(Math.random() * (right - left + 1));
// 1: swap random index and right
swap(unique, right, randomIndex);
// 2 : now the unique[right] is pivot
int pivotValue = unique[right];
int pivotIndex = left;
for (int i = left; i < right; i++) {
if (valueToCount.get(unique[i]) < valueToCount.get(pivotValue)) {
// move smaller values to the left of pivotIndex
swap(unique, i, pivotIndex++);
}
}
// swap the pivot value with the value at pivotIndex
swap(unique, right, pivotIndex);
return pivotIndex;
}
public void swap(int[] unique, int l, int r) {
int temp = unique[l];
unique[l] = unique[r];
unique[r] = temp;
}
}- Quick Select: O(n) average case, O(n²) worst case
- Quick Sort: O(n log n) average case, O(n²) worst case
In the code snippets provided earlier, the pivot element for Quick Sort and Quick Select is chosen to be the last element in the subarray being sorted. This is a simple and efficient way to choose a pivot element, but it can lead to worst-case behavior if the input array is already sorted or nearly sorted.
Eg, the partitioning step will always choose the first element as the pivot element, and the loop will move all the elements to the right of the pivot element. This means that the partitioning step will only move the pivot element one position to the right.
public static void quickSort(int[] arr, int left, int right) {
if (left < right) {
int pivotIndex = partition(arr, left, right);
quickSort(arr, left, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, right);
}
}
private static int partition(int[] arr, int left, int right) {
int pivot = arr[right];
int i = left;
for (int j = left; j < right; j++) {
if (arr[j] <= pivot) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
}
}
int temp = arr[i];
arr[i] = arr[right];
arr[right] = temp;
return i;
}quick select and quick sort algo is the same except that quick select will discard half of the array each time according to the pivotIndex value.
Leetcode 43 Multiply Strings
Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.
Example 1:
Input: num1 = "2", num2 = "3"
Output: "6"Example 2:
Input: num1 = "123", num2 = "456"
Output: "56088"Note:
- The length of both
num1andnum2is < 110. - Both
num1andnum2contain only digits0-9. - Both
num1andnum2do not contain any leading zero, except the number 0 itself. - You must not use any built-in BigInteger library or convert the inputs to integer directly.ma
Leet code 780 Reaching Points
A move consists of taking a point (x, y) and transforming it to either (x, x+y) or (x+y, y).
Given a starting point (sx, sy) and a target point (tx, ty), return True if and only if a sequence of moves exists to transform the point (sx, sy) to (tx, ty). Otherwise, return False.
Examples:
Input: sx = 1, sy = 1, tx = 3, ty = 5
Output: True
Explanation:
One series of moves that transforms the starting point to the target is:
(1, 1) -> (1, 2)
(1, 2) -> (3, 2)
(3, 2) -> (3, 5)Input: sx = 1, sy = 1, tx = 2, ty = 2
Output: FalseInput: sx = 1, sy = 1, tx = 1, ty = 1
Output: True
We work backwards to find the answer, trying to transform the target point to the starting point via applying the parent operation (x, y) -> (x-y, y) or (x, y-x) depending on which one doesn't have negative coordinates.
First, we keep reducing tx and ty to values until one of the tx==sx or ty==sy. At this point, we know we are at a point located either horizontal from the source or vertical from the source.
So if it is located horizontally away from source, then ty==sy will be true. So we keep reducing tx value. We see if we can move from tx to sx with ty steps.
Leetcode 300 Longest Increasing Subsequence
Given an unsorted array of integers, find the length of longest increasing subsequence.
Example:
Input: [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.class Solution {
public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length]; // dp[i]: max length if we must include number at ith position
Arrays.fill(dp, 1); // need to initialise to 1 since this is the min max length if we include the number at i
int max = 1;
for(int n=1; n<nums.length; n++){
for(int j=n-1 ; j>=0; j--){
if(nums[n]>nums[j]){
dp[n]=Math.max(dp[n], dp[j]+1);
}
}
max = Math.max(max, dp[n]);
}
return max;
}
}We need to have a variable max instead of returning dp[last index] because the last element might not be included in the longest sequence.
Leet code 775. Global and Local Inversions
We have some permutation A of [0, 1, ..., N - 1], where N is the length of A.
The number of (global) inversions is the number of i < j with 0 <= i < j < N and A[i] > A[j].
The number of local inversions is the number of i with 0 <= i < N and A[i] > A[i+1].
Return true if and only if the number of global inversions is equal to the number of local inversions.
- NOTE THAT: The values in the array are 0,1…n
Example 1:
Input: A = [1,0,2]
Output: true
Explanation: There is 1 global inversion, and 1 local inversion.Example 2:
Input: A = [1,2,0]
Output: false
Explanation: There are 2 global inversions, and 1 local inversion.
1249. Minimum Remove to Make Valid Parentheses
Given a string s of '(' , ')' and lowercase English characters.
Your task is to remove the minimum number of parentheses ( '(' or ')', in any positions ) so that the resulting parentheses string is valid and return any valid string.
Formally, a parentheses string is valid if and only if:
- It is the empty string, contains only lowercase characters, or
- It can be written as
AB(Aconcatenated withB), whereAandBare valid strings, or - It can be written as
(A), whereAis a valid string.
Example 1:
Input: s = "lee(t(c)o)de)"
Output: "lee(t(c)o)de"
Explanation: "lee(t(co)de)" , "lee(t(c)ode)" would also be accepted.Example 2:
Input: s = "a)b(c)d"
Output: "ab(c)d"Example 3:
Input: s = "))(("
Output: ""
Explanation: An empty string is also valid.Example 4:
Input: s = "(a(b(c)d)"
Output: "a(b(c)d)"
- Use a stack to track the indices of the open brackets.
- Whenever you see a closing bracket, pop one out of the stack. If the stack is empty, it means we are dealing with an extra closing bracket. However, we do not immediately remove it. Instead, we do a lazy deletion by substituting it with a symbol #. This is because, later on, when we want to remove the open brackets, the indices is based on the original string. Hence, we want these indices to remain valid.
- At the end of going through all characters, if there are excess open brackets in the stack, we will then need to remove them.
- At the last part, we remove the closing brackets that were lazily removed previously by doing a replaceAll(“#”, “”).
- Note that the commented lines are the same as line 37. However, it is less efficient that line 37 as it does not pass the last test case on leet code.
// Another attempt...that is correct.
class Solution {
public String minRemoveToMakeValid(String s) {
String result = "";
Stack<Integer> open = new Stack<>();
for(int i=0; i<s.length(); i++){
if(s.charAt(i) == '('){
open.push(i);
result += "(";
} else if (s.charAt(i) == ')'){
if(open.size()>0){
result+=")";
open.pop();
} else{
result+="&"; // we don't immediately remove ) from result
// even though we will remove it ultimately..this is to make sure that the index
// of open is valid for all (
}
} else {
result += s.substring(i, i+1);
}
}
// Remove all the open bracket
while(open.size()>0){
int pos = open.pop();
if((pos+1)<=result.length()-1){
result=result.substring(0, pos) + "#"+result.substring(pos+1);
} else{
result=result.substring(0, pos) + "#";
}
}
return result.replaceAll("#", "").replaceAll("&", "");
}
}// better solution
class Solution {
public String minRemoveToMakeValid(String s) {
int count=0;
char[] stringChar = s.toCharArray();
for(int i=0; i<stringChar.length; i++){
if(stringChar[i] == '('){
count++;
} else if (stringChar[i] == ')'){
if(count>0){
count--;
} else {
stringChar[i]='#';
}
}
}
for(int i=stringChar.length-1; i>=0; i--){
if(count==0){
break;
}
if(stringChar[i] == '('){
stringChar[i]='#'; // reason why we don't set as '' is because
// empty char literal is not allowed
count--;
}
}
return new String(stringChar).replaceAll("#", "");
}
}301. Remove Invalid Parentheses **
Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.
Note: The input string may contain letters other than the parentheses ( and ).
Example 1:
Input: "()())()"
Output: ["()()()", "(())()"]Example 2:
Input: "(a)())()"
Output: ["(a)()()", "(a())()"]Example 3:
Input: ")("
Output: [""]
The idea is to make use of recursion to remove brackets from the string. As long as the current string is not valid, we try to remove one character at different positions from the string (For loop in line 35–39).
Then, once we have a valid string, we add to results, provided that we checked it is the minimum.
Line 29 might not be needed actually.
The seenBefore Hash Set is to help in the time complexity where we store all those strings arrangements that we have seen before. This helps make sure we do not repeat recursion calls on the same strings.
class Solution {
HashSet<String> seenBefore;
List<String> result;
int maxLen;
public List<String> removeInvalidParentheses(String s) {
seenBefore = new HashSet<>();
result = new LinkedList<>();
maxLen=0;
remove(s);
return result;
}
public void remove(String s){
if(seenBefore.contains(s)) return;
seenBefore.add(s);
if(isValid(s)){
if(s.length()>maxLen){
maxLen=s.length();
result = new LinkedList<>();
result.add(s);
} else if (s.length() == maxLen){
result.add(s);
}
return;
}
for(int i=0; i<s.length(); i++){
String removedBrack = s.substring(0, i)+s.substring(i+1);
remove(removedBrack);
}
}
public boolean isValid(String s){
int count=0;
for(int i=0; i<s.length(); i++){
if(s.charAt(i) == '('){
count++;
} else if(s.charAt(i) == ')'){
if(count>0){
count--;
} else {
return false;
}
}
}
return count==0;
}
}921. Minimum Add to Make Parentheses Valid **
Given a string S of '(' and ')' parentheses, we add the minimum number of parentheses ( '(' or ')', and in any positions ) so that the resulting parentheses string is valid.
Formally, a parentheses string is valid if and only if:
- It is the empty string, or
- It can be written as
AB(Aconcatenated withB), whereAandBare valid strings, or - It can be written as
(A), whereAis a valid string.
Given a parentheses string, return the minimum number of parentheses we must add to make the resulting string valid.
Example 1:
Input: "())"
Output: 1Example 2:
Input: "((("
Output: 3Example 3:
Input: "()"
Output: 0Example 4:
Input: "()))(("
Output: 4
Line 10: Found a match
Line 11: If the program enters here, it means there is not enough openBrack to match the current close bracket. Hence, need to add one more open ‘(’ bracket.
Line 17: toAddCloseBrack contains the number of unmatched ‘(’ brackets. Hence, this variable tells us the number of close ‘)’ brackets to add.
32. Longest Valid Parentheses
Pretty challenging
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
Example 1:
Input: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".Example 2:
Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()".Example 3:
Input: s = ""
Output: 0Leet Code Solution:
The ith element of dp represents the length of the longest valid substring ending at ith index.
Now, it’s obvious that the valid substrings must end with ‘)’. This further leads to the conclusion that the substrings ending with ‘(’ will always contain ‘0’ at their corresponding dp indices. Thus, we update the dp array only when ‘)’ is encountered.
i-dp[i-1] gives us the starting position of the previous valid string. We do a -1 to i-dp[i-1] to get the character before it.
- If the character at i-1 is a ‘)’, then we check where is the starting index of the valid substring that ends with i-1? This is given by i-dp[i-1].
- Then, we want to know if there is a ‘( in front of this valid substring. So we check i-dp[i-1]-1 and check if it is == ‘(’.
- If yes, then we need to check the value of dp at the position i-dp[i-1]-2 (olive bracket). If the value dp[i-dp[i-1–2] was previously ≥ 2, then we can add this value (olive)+ 2 (pink and lime green current matching brackets) + most recent valid substring (blue brackets) given by dp[i-1].
Leetcode solution
public class Solution {
public int longestValidParentheses(String s) {
int maxans = 0;
Stack<Integer> stack = new Stack<>(); // either the previous invalid point
// or the previous (
stack.push(-1);
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
stack.push(i); // This will be popped later when we see )
} else {
stack.pop(); // remove the index of previous (, so we can compute len
if (stack.empty()) {
stack.push(i); // why? to mark i as the most recent invalid. So later,
// when we compute length, it will start from i.
} else {
maxans = Math.max(maxans, i - stack.peek());
}
}
}
return maxans;
}
}
20. Valid Parentheses
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
- Every close bracket has a corresponding open bracket of the same type.
Example 1:
Input: s = "()"
Output: trueExample 2:
Input: s = "()[]{}"
Output: trueExample 3:
Input: s = "(]"
Output: falseclass Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for(int i=0; i<s.length(); i++){
char c = s.charAt(i);
if(c=='(' || c=='{' || c == '['){
stack.push(c);
} else {
if(stack.size()<=0) return false;
char exist = stack.pop();
if((exist=='(' && c !=')') || (exist=='{' && c !='}')|| (exist == '[' && c != ']')){
return false;
}
}
}
return stack.size()==0;
}
}Basic Calculator I
Implement a basic calculator to evaluate a simple expression string.
The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .
Example 1:
Input: "1 + 1"
Output: 2Example 2:
Input: " 2-1 + 2 "
Output: 3Example 3:
Input: "(1+(4+5+2)-3)+(6+8)"
Output: 23This question was quite hard…referred to leetcode solution.
Leet code solution: https://leetcode.com/problems/basic-calculator/discuss/62361/Iterative-Java-solution-with-stack
Simple iterative solution by identifying characters one by one. One important thing is that the input is valid, which means the parentheses are always paired and in order.
Only 5 possible input we need to pay attention:
- digit: it should be one digit from the current number
- ‘+’: number is over, we can add the previous number and start a new number
- ‘-’: same as above
- ‘(‘: push the previous result and the sign into the stack, set result to 0, just calculate the new result within the parenthesis.
- ‘)’: pop out the top two numbers from stack, first one is the sign before this pair of parenthesis, second is the temporary result before this pair of parenthesis. We add them together.
Finally if there is only one number, from the above solution, we haven’t add the number to the result, so we do a check see if the number is zero.
class Solution {
public int calculate(String s) {
Stack<Integer> stack = new Stack<Integer>();
int operand = 0;
int result = 0; // For the on-going result
int sign = 1; // 1 means positive, -1 means negative
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (Character.isDigit(ch)) {
// Forming operand, since it could be more than one digit
operand = 10 * operand + (int) (ch - '0');
} else if (ch == '+') {
// Evaluate the expression to the left,
// with result, sign, operand
result += sign * operand;
// Save the recently encountered '+' sign
sign = 1;
// Reset operand
operand = 0;
} else if (ch == '-') {
result += sign * operand;
sign = -1;
operand = 0;
} else if (ch == '(') {
// Push the result and sign on to the stack, for later
// We push the result first, then sign
stack.push(result);
stack.push(sign);
// Reset operand and result, as if new evaluation begins for the new sub-expression
sign = 1;
result = 0;
} else if (ch == ')') {
// Evaluate the expression to the left
// with result, sign and operand
result += sign * operand;
// ')' marks end of expression within a set of parenthesis
// Its result is multiplied with sign on top of stack
// as stack.pop() is the sign before the parenthesis
result *= stack.pop();
// Then add to the next operand on the top.
// as stack.pop() is the result calculated before this parenthesis
// (operand on stack) + (sign on stack * (result from parenthesis))
result += stack.pop();
// Reset the operand
operand = 0;
}
}
return result + (sign * operand);
}
}
Basic Calculator II (Medium)
Implement a basic calculator to evaluate a simple expression string.
The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.
Example 1:
Input: "3+2*2"
Output: 7Example 2:
Input: " 3/2 "
Output: 1Example 3:
Input: " 3+5 / 2 "
Output: 5The solution given by leetcode is good. (refer to it for explanation). The hard part about this is figuring how to do * and / before + and -.
We know that there could be 4 types of operations — addition (+), subtraction (-), multiplication (*) and division (/). Without parenthesis, we know that, multiplication (*) and (\) operations would always have higher precedence than addition (+) and subtraction (-) based on operator precedence rules.
If we look at the above examples, we can make the following observations
- If the current operation is addition
(+)or subtraction(-), then the expression is evaluated based on the precedence of the next operation.
In example 1, 4+3 is evaluated later because the next operation is multiplication (3*5) which has higher precedence. But, in example 2, 4+3 is evaluated first because the next operation is subtraction (3-5) which has equal precedence.
- If the current operator is multiplication
(*)or division(/), then the expression is evaluated irrespective of the next operation. This is because in the given set of operations(+,-,*,/), the*and/operations have the highest precedence and therefore must be evaluated first.
……..refer to leetcode solutions……….
class Solution {
public int calculate(String s) {
Stack<Integer> stack = new Stack<>();
int prevNum = 0;
char prevSign = '+';
for(int i=0; i<s.length(); i++){
char current = s.charAt(i);
if(Character.isDigit(current)){
prevNum = (prevNum * 10) + (current - '0');
}
if ((!Character.isDigit(current) && !Character.isWhitespace(current)) || i==s.length()-1){
if (prevSign == '+'){
// A + B
// stack is empty
// prevSign = + (The one set by default)
// prevNum = A
// Now at +
stack.push(prevNum);
} else if (prevSign == '-'){
stack.push(-1 * prevNum);
} else if (prevSign == '*'){
// we are already at the next char
// eg, A * B + C
// Currently, we are at +
// A is in the stack, * is prevSign and B is prevNum
stack.push(stack.pop() * prevNum);
} else if (prevSign == '/'){
stack.push(stack.pop() / prevNum);
}
prevSign = current;
prevNum = 0;
}
}
int result = 0;
while(!stack.isEmpty()){
result += stack.pop();
}
return result;
}
}
// Idea: When you see a number, just add it to prevNum
// When you see operator like + or -, push the prevNum value to stack
// When you see * or /, start to evaluate the values...
// The reason why we check for prevSign is because for * and /, we can only start to
// evaluate when we finish looking at x * yWhen we encounter a new operator, we will then go on to evaluate the previous operator seen before (stored in the variable operation). According to the sign of the previous operator, it will evaluate the value stored in previousNum which is the number that comes after the previous operator.
Eg, 1+2
- Set
previousNumto 1 - See that current char is + then we see that previous operator is +. Hence, push 1 to stack. Set
operationto + andpreviousNumto 0. - set
previousNumto 2. See that previous char is +. Push 2 into stack.
When we exit from the for loop, we will then proceed to add up all the numbers in the stack.
Basic Calculator III
Implement a basic calculator to evaluate a simple expression string.
The expression string contains only non-negative integers, '+', '-', '*', '/' operators, and open '(' and closing parentheses ')'. The integer division should truncate toward zero.
You may assume that the given expression is always valid. All intermediate results will be in the range of [-231, 231 - 1].
Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().
Example 1:
Input: s = "1+1"
Output: 2Example 2:
Input: s = "6-4/2"
Output: 4Example 3:
Input: s = "2*(5+5*2)/3+(6/2+8)"
Output: 21// First attempt...incorrect
class Solution {
public int calculate(String s) {
int prevNum = 0;
char prevSign = '+';
Stack<Integer> stack = new Stack<>();
int i=0;
while(i<s.length()){
char curr = s.charAt(i);
if(Character.isDigit(curr)){
prevNum = ( prevNum * 10 ) + (curr - '0');
} else if (curr == '('){
// do recursion
int start = i;
int end = i;
char c = curr;
int countOfOpen = 1;
while(c != ')' && countOfOpen >= 1){
c = s.charAt(end);
if (c == '('){
countOfOpen ++;
}
if (c ==')'){
countOfOpen--;
}
end++;
}
String str = s.substring(start+1, end);
int value = calculate(str);
prevNum = value;
i = end;
continue;
}
if (!Character.isDigit(curr) || i == s.length()-1){
if (prevSign == '+'){
stack.push(prevNum);
} else if (prevSign == '-'){
stack.push(-1 * prevNum);
} else if (prevSign == '*'){
stack.push(stack.pop() * prevNum);
} else if (prevSign == '/'){
stack.push(stack.pop() / prevNum);
}
prevSign = curr;
prevNum = 0;
}
i++;
}
int result = prevNum;
while(!stack.isEmpty()){
result += stack.pop();
}
return result;
}
}// Second attempt... correct
class Solution {
public int calculate(String s) {
int prevNum = 0;
char prevSign = '+';
Stack<Integer> stack = new Stack<>();
int i=0;
while(i<s.length()){
char curr = s.charAt(i);
if(Character.isDigit(curr)){
prevNum = ( prevNum * 10 ) + (curr - '0');
} else if (curr == '('){
// do recursion
int start = i;
int end = i+1;
char c = curr;
int countOfOpen = 1;
// Trying to find the section between the two outermost brackets
while(end < s.length()){
c = s.charAt(end);
if (c == '('){
countOfOpen ++;
}
if (c ==')'){
countOfOpen--;
}
if (countOfOpen == 0) break; // This check needs to be here instead of while condition so that end don't get incremented unnecessarily
end++;
}
String str = s.substring(start+1, end); // exclude the brackets at the both ends
int value = calculate(str);
prevNum = value; // treat whatever value inside the brackets to be a number value.
i = end;
continue; // move to the next index
}
if (!Character.isDigit(curr) || i == s.length()-1){
if (prevSign == '+'){
stack.push(prevNum);
} else if (prevSign == '-'){
stack.push(-1 * prevNum);
} else if (prevSign == '*'){
stack.push(stack.pop() * prevNum);
} else if (prevSign == '/'){
stack.push(stack.pop() / prevNum);
}
prevSign = curr;
prevNum = 0;
}
i++;
}
int result = prevNum;
while(!stack.isEmpty()){
result += stack.pop();
}
return result;
}
}
This is similar to the previous basic calculator II except that we pass the string in the bracket to a recursion function…kind of outsourcing…
Should memorise how basic calculator II works.
Basic Calculator IV
Given an expression such as expression = "e + 8 - a + 5" and an evaluation map such as {"e": 1} (given in terms of evalvars = ["e"] and evalints = [1]), return a list of tokens representing the simplified expression, such as ["-1*a","14"]
- An expression alternates chunks and symbols, with a space separating each chunk and symbol.
- A chunk is either an expression in parentheses, a variable, or a non-negative integer.
- A variable is a string of lowercase letters (not including digits.) Note that variables can be multiple letters, and note that variables never have a leading coefficient or unary operator like
"2x"or"-x".
Expressions are evaluated in the usual order: brackets first, then multiplication, then addition and subtraction.
- For example,
expression = "1 + 2 * 3"has an answer of["7"].
The format of the output is as follows:
- For each term of free variables with a non-zero coefficient, we write the free variables within a term in sorted order lexicographically.
- For example, we would never write a term like
"b*a*c", only"a*b*c". - Terms have degrees equal to the number of free variables being multiplied, counting multiplicity. We write the largest degree terms of our answer first, breaking ties by lexicographic order ignoring the leading coefficient of the term.
- For example,
"a*a*b*c"has degree4. - The leading coefficient of the term is placed directly to the left with an asterisk separating it from the variables (if they exist.) A leading coefficient of 1 is still printed.
- An example of a well-formatted answer is
["-2*a*a*a", "3*a*a*b", "3*b*b", "4*a", "5*c", "-6"]. - Terms (including constant terms) with coefficient
0are not included. - For example, an expression of
"0"has an output of[].
Note: You may assume that the given expression is always valid. All intermediate results will be in the range of [-231, 231 - 1].
Example 1:
Input: expression = "e + 8 - a + 5", evalvars = ["e"], evalints = [1]
Output: ["-1*a","14"]Example 2:
Input: expression = "e - 8 + temperature - pressure", evalvars = ["e", "temperature"], evalints = [1, 12]
Output: ["-1*pressure","5"]Example 3:
Input: expression = "(e + 8) * (e - 8)", evalvars = [], evalints = []
Output: ["1*e*e","-64"]I didn’t solve this problem because i think it won’t be tested in a real interview…also was lazy…below is a solution copied from someone else..will look at this one day.
class Solution:
def basicCalculatorIV(self, expression: str, evalvars: List[str], evalints: List[int]) -> List[str]:
evalMap = {}
for e, v in zip(evalvars, evalints):
evalMap[e] = v
def sum_map(st_map):
res = Counter()
for num_map in st_map:
for k, v in num_map.items():
res[k] += v
return res
def multiply(num1, num2):
res = {}
for k1 in num1.keys():
for k2 in num2.keys():
if num1[k1] == 0 or num2[k2] == 0:
continue
mul_key = []
if k1: mul_key += k1.split("*")
if k2: mul_key += k2.split("*")
mul_key = sorted(mul_key)
key = "*".join(mul_key)
res[key] = res.get(key, 0) + num1[k1] * num2[k2]
return res
## Add space to better separate ().
expression = expression.replace("(", "( ")
expression = expression.replace(")", " )")
s = deque(expression.split(" "))
def dfs():
## use empty "" to denote pure number.
st = []
# last_num = {"": 0}
num = {"": 0}
sign = "+"
while len(s) > 0:
char = s.popleft()
if char.isdigit() or char in evalMap:
if char in evalMap:
number = evalMap[char]
else:
number = int(char)
num = {"": number}
elif char.isalpha():
num = {char: 1}
if char == "(":
num = dfs()
if len(s) == 0 or char in "+-*()":
if sign == "+":
st.append(num)
if sign == "-":
for k, v in num.items():
num[k] = -v
st.append(num)
if sign == "*":
st[-1] = multiply(st[-1], num)
sign = char
if char == ")":
break
return sum_map(st)
resMap = dfs()
# Gather final results.
res, f_num = [], []
keys = list(resMap.keys())
keys = sorted(keys, key=lambda x: (-len(x.split('*')), x.split('*')))
for k in keys:
val = resMap[k]
if val == 0:
continue
if k == "":
f_num = [str(val)]
else:
res.append(str(val) + "*" + k)
return res + f_numLeetcode 616 Add Bold Tags in a String (Leetcode premium qns)
You are given a string s and an array of strings words.
You should add a closed pair of bold tag <b> and </b> to wrap the substrings in s that exist in words.
- If two such substrings overlap, you should wrap them together with only one pair of closed bold-tag.
- If two substrings wrapped by bold tags are consecutive, you should combine them.
Return s after adding the bold tags.
Example 1:
Input: s = "abcxyz123", words = ["abc","123"]
Output: "<b>abc</b>xyz<b>123</b>"
Explanation: The two strings of words are substrings of s as following: "abcxyz123".
We add <b> before each substring and </b> after each substring.Example 2:
Input: s = "aaabbb", words = ["aa","b"]
Output: "<b>aaabbb</b>"
Explanation:
"aa" appears as a substring two times: "aaabbb" and "aaabbb".
"b" appears as a substring three times: "aaabbb", "aaabbb", and "aaabbb".
We add <b> before each substring and </b> after each substring: "<b>a<b>a</b>a</b><b>b</b><b>b</b><b>b</b>".
Since the first two <b>'s overlap, we merge them: "<b>aaa</b><b>b</b><b>b</b><b>b</b>".
Since now the four <b>'s are consecuutive, we merge them: "<b>aaabbb</b>".- The given dict won’t contain duplicates, and its length won’t exceed 100.
- All the strings in input have length in range [1, 1000].
class Solution {
public String addBoldTag(String s, String[] words) {
// iterate through each word in words
// For each word, create a window of the word length
// check if word exist in s..if yes, mark the indexes...
int[] result = new int[s.length()];
for(String w: words){
int windowSize = w.length();
int start=0;
while(start<=s.length()-windowSize){
if(s.substring(start, start+windowSize).equals(w)){
for(int i=start; i<start+windowSize; i++){
result[i] = 1;
}
}
start++;
}
}
String resultString = "";
int r=0;
while(r < result.length){
if(result[r] == 1){
resultString += "<b>" + s.substring(r, r+1);
r++;
while(r < result.length && result[r] == 1){
resultString += s.substring(r, r+1);
r++;
}
resultString += "</b>";
} else{
resultString += s.substring(r, r+1);
r++;
}
}
return resultString;
}
}This solution is pretty easy to understand once you read it. Loop through all the words in the dictionary, then create a window size of that word you are currently looping at.
Attempt to find matches in the original string. When a match is found, mark each individual character in the bold array as true. True means the character is to be bold. False means no.
12. Leetcode 139 Word Break
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
Note:
- The same word in the dictionary may be reused multiple times in the segmentation.
- You may assume the dictionary does not contain duplicate words.
class Solution {
HashMap<String, Boolean> dp;
public boolean wordBreak(String s, List<String> wordDict) {
dp = new HashMap<>();
return recurse(s, wordDict);
}
public boolean recurse(String s, List<String> wordDict){
if(dp.containsKey(s)) return dp.get(s);
if(s.length() == 0){
dp.put(s, true);
return true;
}
if(s.length()<0){
return false;
}
for(String w: wordDict){
if(s.startsWith(w)){
if(recurse(s.substring(w.length()), wordDict)){
dp.put(s, true);
return true;
}
}
}
dp.put(s, false);
return false;
}
}140. Word Break II
Given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in any order.
Note that the same word in the dictionary may be reused multiple times in the segmentation.
Example 1:
Input: s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]
Output: ["cats and dog","cat sand dog"]Example 2:
Input: s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"]
Output: ["pine apple pen apple","pineapple pen apple","pine applepen apple"]
Explanation: Note that you are allowed to reuse a dictionary word.Example 3:
Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: []class Solution {
public:
unordered_map<string, vector<string>> dp;
vector<string> wordBreak(string s, vector<string>& wordDict) {
return recurse(s, wordDict);
}
vector<string> recurse(string s, vector<string>& wordDict) {
if (dp.count(s) > 0)
return dp[s];
if (s.length() == 0)
return {""};
vector<string> result;
for (string word : wordDict) {
if (s.substr(0, word.length()) == word) {
vector<string> subResult = recurse(s.substr(word.length()), wordDict);
for (string sub : subResult) {
if (sub == "")
result.push_back(word);
else
result.push_back(word + " " + sub);
}
}
}
dp[s] = result;
return result;
}
};Time complexity: O(n*m) where n is the length of the input and m is the size of wordDict.
In the recurse function, for each substring of s, it iterates over all words in the word dictionary to check if the substring starts with any of those words. This iteration takes O(M) time. If the substring matches a word, the function recursively calls itself on the remaining substring. In the worst case, where the substring matches all words in the word dictionary, the function will make recursive calls for each word, resulting in O(N) recursive calls.
The following questions below makes use of Prefix Sum and Hash Map. Good to be able to spot what type of questions needs this.
Leet Code 974. 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]https://www.youtube.com/watch?v=u9m-hnlcydk
When we have X%k=2 and Y%k=2, we get (X-Y)%k = 0.
The idea behind this solution is to calculate the cumulative sum of the items in the given array. For eg, at index i we have the sum of the numbers from position 0,1..i. Then for each index, we store the value of cumulative sum % K.
If we have C counts with remainder 2, then total number of subarrays with remainder 0 derived from the subtraction of the cumulative sums with remainder 2 can be visualised as a C Choose 2 problem.
We choose any two points and take their difference to give a remainder of 0. (see image above). The value of the map represents the number of subarrays with their remainder being the key value. we simply choose any 2 arrays within it and we will find a subarray that gives remainder 0. Thus, the problem is a C Choose 2 problem.
The special case is if we have C counts with remainder 0, where the total number of subarrays with remainder 0 will be C + C Choose 2. C -> The number of subarrays with already existing remainder 0. The C Choose 2 would be the combination of any 2 subarrays.
Hence, in the code above, we store count (key) and their associated remainder (value) in a hashmap. Formula of C Choose 2 is given to be C*(C-1)/2.
1010. Pairs of Songs With Total Durations Divisible by 60
You are given a list of songs where the ith song has a duration of time[i] seconds.
Return the number of pairs of songs for which their total duration in seconds is divisible by 60. Formally, we want the number of indices i, j such that i < j with (time[i] + time[j]) % 60 == 0.
Example 1:
Input: time = [30,20,150,100,40]
Output: 3
Explanation: Three pairs have a total duration divisible by 60:
(time[0] = 30, time[2] = 150): total duration 180
(time[1] = 20, time[3] = 100): total duration 120
(time[1] = 20, time[4] = 40): total duration 60Example 2:
Input: time = [60,60,60]
Output: 3
Explanation: All three pairs have a total duration of 120, which is divisible by 60.Constraints:
1 <= time.length <= 6 * 1041 <= time[i] <= 500
class Solution {
public int numPairsDivisibleBy60(int[] time) {
int count = 0;
int sum = time[0];
Map<Integer, Integer> map = new HashMap<>(); // remainder to count of vals in time with this remainder
map.put(sum%60, 1);
for(int t=1; t<time.length; t++){
int remainder = time[t]%60;
int other = Math.abs(60-remainder);
// if a value does not have remainder
// 0 when divided by 60, then we need to add it to another number with the
// "opposite" remainder(60-re) so that their sum gives remainder of 0
count+=map.getOrDefault(other, 0);
if(remainder == 0){
count+=map.getOrDefault(remainder, 0);
}
int currCount = map.getOrDefault(remainder, 0);
map.put(remainder, currCount+1);
}
return count;
}
}LeetCode 560. Subarray Sum Equals K
Given an array of integers nums and an integer k, return the total number of continuous subarrays whose sum equals to k.
Example 1:
Input: nums = [1,1,1], k = 2
Output: 2Example 2:
Input: nums = [1,2,3], k = 3
Output: 2
Leet Code 1658. Minimum Operations to Reduce X to Zero
You are given an integer array nums and an integer x. In one operation, you can either remove the leftmost or the rightmost element from the array nums and subtract its value from x. Note that this modifies the array for future operations.
Return the minimum number of operations to reduce x to exactly 0 if it's possible, otherwise, return -1.
Example 1:
Input: nums = [1,1,4,2,3], x = 5
Output: 2
Explanation: The optimal solution is to remove the last two elements to reduce x to zero.Example 2:
Input: nums = [5,6,7,8,9], x = 4
Output: -1Example 3:
Input: nums = [3,2,20,1,1,3], x = 10
Output: 5
Explanation: The optimal solution is to remove the last three elements and the first two elements (5 operations in total) to reduce x to zero.This question is quite similar to the one above involving the use of prefix sum.
- Very important to identify this problem to be like the problem involving prefix sum and map.
Leet Code 1477. Find Two Non-overlapping Sub-arrays Each With Target Sum
Given an array of integers arr and an integer target.
You have to find two non-overlapping sub-arrays of arr each with sum equal target. There can be multiple answers so you have to find an answer where the sum of the lengths of the two sub-arrays is minimum.
Return the minimum sum of the lengths of the two required sub-arrays, or return -1 if you cannot find such two sub-arrays.
Example 1:
Input: arr = [3,2,2,4,3], target = 3
Output: 2
Explanation: Only two sub-arrays have sum = 3 ([3] and [3]). The sum of their lengths is 2.Example 2:
Input: arr = [7,3,4,7], target = 7
Output: 2
Explanation: Although we have three non-overlapping sub-arrays of sum = 7 ([7], [3,4] and [7]), but we will choose the first and third sub-arrays as the sum of their lengths is 2.Example 3:
Input: arr = [4,3,2,6,2,3,4], target = 6
Output: -1
Explanation: We have only one sub-array of sum = 6.Example 4:
Input: arr = [5,5,4,4,5], target = 3
Output: -1
Explanation: We cannot find a sub-array of sum = 3.Example 5:
Input: arr = [3,1,1,1,5,1,2,1], target = 3
Output: 3
Explanation: Note that sub-arrays [1,2] and [2,1] cannot be an answer because they overlap.This problem uses prefix sum and the Transactions Stock (At most k Transaction) idea.
At position i, we visualise as cutting the array into two partition. [0,1…i] and [i+1, i+2…]. For each i, we compute the total length of the subarrays (that sums to target) in these 2 partitions. For each i, we track the minimum length and return that.
length = MIN {leftIndex[i] + rightIndex[i]} for each i value
Hence, we need to first use the idea of prefix sum to obtain values at every i position for leftIndex and rightIndex.
rightIndex[i] contains min length of subarray that sums up to target from position rightIndex.length-1, rightIndex.length-2,…i+1.
leftIndex[i] contains min length of subarray that sums up to target from position 0,1…i.
Leet Code 713. Subarray Product Less Than K
Your are 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.This is a Sliding Window Question.
1524. Number of Sub-arrays With Odd Sum
Given an array of integers arr. Return the number of sub-arrays with odd sum.
As the answer may grow large, the answer must be computed modulo 10^9 + 7.
Example 1:
Input: arr = [1,3,5]
Output: 4
Explanation: All sub-arrays are [[1],[1,3],[1,3,5],[3],[3,5],[5]]
All sub-arrays sum are [1,4,9,3,8,5].
Odd sums are [1,9,3,5] so the answer is 4.Example 2:
Input: arr = [2,4,6]
Output: 0
Explanation: All sub-arrays are [[2],[2,4],[2,4,6],[4],[4,6],[6]]
All sub-arrays sum are [2,6,12,4,10,6].
All sub-arrays have even sum and the answer is 0.Example 3:
Input: arr = [1,2,3,4,5,6,7]
Output: 16Example 4:
Input: arr = [100,100,99,99]
Output: 4Example 5:
Input: arr = [7]
Output: 1ODD — ODD = EVEN
ODD — EVEN = ODD
EVEN — ODD = ODD
EVEN — EVEN = EVEN
class Solution {
public int numOfSubarrays(int[] arr) {
// odd - odd = even
// odd - even = odd
// even - odd = odd
// even - even = even
int oddCount = 0;
int evenCount = 0;
int count = 0;
int sum=0;
int mod = (int)1e9 + 7;
for(int i=0; i<arr.length; i++){
sum+=arr[i];
int remainder = sum%2;
if(remainder<0){
remainder += 2;
}
if(remainder == 0){
count += (oddCount) % mod;
evenCount++;
} else {
count = (count+1) % mod;
count += (evenCount) % mod;
oddCount++;
}
}
return count % mod;
}
}Hackerank Pairs
Pairs
LeetCode 5 Longest Palindrome Substring
Given a string s, return the longest palindromic substring in s.
Example 1:
Input: s = "babad"
Output: "bab"
Note: "aba" is also a valid answer.Example 2:
Input: s = "cbbd"
Output: "bb"
This is actually complicated.
Leet Code 516. Longest Palindromic Subsequence
Given a string s, find the longest palindromic subsequence’s length in s. You may assume that the maximum length of s is 1000.
Example 1:
Input:
"bbbab"Output:
4One possible longest palindromic subsequence is “bbbb”.
Example 2:
Input:
"cbbd"Output:
2One possible longest palindromic subsequence is “bb”.
class Solution {
public int longestPalindromeSubseq(String s) {
int[][] dp = new int[s.length()][s.length()];
for(int i=0; i<s.length(); i++){
dp[i][i]=1;
}
for(int len=2; len<=s.length(); len++){
for(int i=0; i<=s.length()-len; i++){
int j=i+len-1;
if(s.charAt(i) == s.charAt(j)){
dp[i][j]=dp[i+1][j-1]+2;
} else {
dp[i][j]=Math.max(dp[i+1][j], dp[i][j-1]);
}
}
}
return dp[0][s.length()-1];
}
}- Initialised the diagonal values of the dp array to 1 (since a single character is always a palindrome)
- Variables i and j to represent the start and end indices of the subsequence being considered
Why is the formula dp[i][j]=Math.max(dp[i+1][j], dp[i][j-1]);
Say we have string “agbdba”
When we are considering palindrome for length 3, we will check if a and b are the same. If not, then we either take ag or gb, to indicate this is the max length of subsequence.
ag -> 0,1, dp[i][j-1]
gb -> 1,2, dp[i+1][j]
agb -> 0,2, dp[i][j]
If we consider length 4, for 0–3 we will look at 0–2 or 1–3 indexes.
Leet Code 9: Palindrome Number
Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.
Follow up: Could you solve it without converting the integer to a string?
Example 1:
Input: x = 121
Output: trueExample 2:
Input: x = -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.Example 3:
Input: x = 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.Example 4:
Input: x = -101
Output: falseThe first step is to find out the number of digits that the given input has and determine if it is an odd or even number.
Then, we add the last half of the digit into a number and compare with the first half.
Note that negative values are not palindromes.
Leet Code Solution:
public class Solution {
public bool IsPalindrome(int x) {
// Special cases:
// As discussed above, when x < 0, x is not a palindrome.
// Also if the last digit of the number is 0, in order to be a palindrome,
// the first digit of the number also needs to be 0.
// Only 0 satisfy this property.
if(x < 0 || (x % 10 == 0 && x != 0)) {
return false;
}
int revertedNumber = 0;
while(x > revertedNumber) {
revertedNumber = revertedNumber * 10 + x % 10;
x /= 10;
}
// When the length is an odd number, we can get rid of the middle digit by revertedNumber/10
// For example when the input is 12321, at the end of the while loop we get x = 12, revertedNumber = 123,
// since the middle digit doesn't matter in palidrome(it will always equal to itself), we can simply get rid of it.
return x == revertedNumber || x == revertedNumber/10;
}
}Leet Code 336. Palindrome Pairs (Hard)
Given a list of unique words, return all the pairs of the distinct indices (i, j) in the given list, so that the concatenation of the two words words[i] + words[j] is a palindrome.
Example 1:
Input: words = ["abcd","dcba","lls","s","sssll"]
Output: [[0,1],[1,0],[3,2],[2,4]]
Explanation: The palindromes are ["dcbaabcd","abcddcba","slls","llssssll"]Example 2:
Input: words = ["bat","tab","cat"]
Output: [[0,1],[1,0]]
Explanation: The palindromes are ["battab","tabbat"]Example 3:
Input: words = ["a",""]
Output: [[0,1],[1,0]]The first solution is brute force where we go trough each pair of words and check if their concatenation forms a palindrome.
In the following solution, it is much simpler.
There are some cases that we need to consider.
- If a word is ABC, we check if it’s reverse CBA exists in the given words.
- If a word is an empty string, any string that is a palindrome will become a pair with it.
- Otherwise, we have XXBC string. Say, if XX is a palindrome, then if we can find CB in words, we will be able to form a pair. Hence, what we need to do is to check from position 0 to k and see if it is a palindrome, then we check if CB exists.
- Or, if we have CBXX string. Say if XX is palindrome, then we need to find BC in words to form a pair.
We make use of hashMap to help us.
class Solution {
public List<List<Integer>> palindromePairs(String[] words) {
List<List<Integer>> output = new ArrayList<>();
Map<String, Integer> lookup = new HashMap<>();
int n = words.length;
for (int i = 0; i < n; i++) {
String word = words[i];
lookup.put(word, i);
}
for (int i = 0; i < n; i++) {
String word = words[i];
if (word.equals("")) {
for (int j = 0; j < n; j++) {
if (i != j && isPal(words[j], 0, words[j].length() - 1)) {
output.add(Arrays.asList(i, j));
output.add(Arrays.asList(j, i));
}
}
continue;
}
String bw = new StringBuilder(word).reverse().toString(); // String builder is more efficient
if (lookup.containsKey(bw) && lookup.get(bw) != i) {
output.add(Arrays.asList(i, lookup.get(bw)));
}
for (int k = 1; k < word.length(); k++) {
if (isPal(word, 0, k - 1) && lookup.containsKey(new StringBuilder(word.substring(k)).reverse().toString())) {
output.add(Arrays.asList(lookup.get(new StringBuilder(word.substring(k)).reverse().toString()), i));
}
// Note the ordering is different from above
if (isPal(word, k, word.length() - 1) && lookup.containsKey(new StringBuilder(word.substring(0, k)).reverse().toString())) {
output.add(Arrays.asList(i, lookup.get(new StringBuilder(word.substring(0, k)).reverse().toString())));
}
}
}
return output;
}
private boolean isPal(String w, int st, int end) {
while (st < end) {
if (w.charAt(st) != w.charAt(end)) {
return false;
}
st++;
end--;
}
return true;
}
}
131. Palindrome Partitioning
Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.
A palindrome string is a string that reads the same backward as forward.
Example 1:
Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]Example 2:
Input: s = "a"
Output: [["a"]]
The param index is the starting index.
O(n) complexity in each recursion call.
Max recursion depth is n — length of string. O(n) calls each.
Total complexity: O(n*n)
Or…alternative solution
class Solution {
public List<List<String>> partition(String s) {
return partitionHelper(s);
}
public List<List<String>> partitionHelper(String s){
List<List<String>> result = new LinkedList<>();
for(int i=1; i<s.length()+1; i++){
String str = s.substring(0, i);
if(isPal(str)){
if (i==s.length()){
// the case where s is the entire string .. no need to recurse anymore
List<String> temp = new LinkedList<>();
temp.add(str);
result.add(temp);
} else {
List<List<String>> remainder = partitionHelper(s.substring(i));
if(remainder.size() != 0){
for(List<String> each: remainder){
each.add(0, str);
result.add(each);
}
}
}
}
}
return result;
}
public boolean isPal(String s){
int start = 0;
int end = s.length()-1;
while(start<end){
if(s.charAt(start) != s.charAt(end)) return false;
start++;
end--;
}
return true;
}
}How can we improve?
We can further optimize the approach by using dynamic programming to determine if a string is a palindrome in constant time.
We use a 2 Dimensional array dp of size N⋅N where,
dp[start][end] = true , if the substring beginning at index start and ending at index end is a palindrome.
Otherwise, dp[start][end] == false.
Also, we must update the dp array, if we find that the current string is a palindrome.
132. Palindrome Partitioning II
Given a string s, partition s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
Example 1:
Input: s = "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.Example 2:
Input: s = "a"
Output: 0Example 3:
Input: s = "ab"
Output: 1
class Solution {
int[] cutsDp;
boolean[][] palindromeDp;
public int minCut(String s) {
cutsDp = new int[s.length()]; // min cuts from 0 till i
palindromeDp = new boolean[s.length()][s.length()];
buildPalindromeDp(s, s.length());
for(int end=0; end<s.length(); end++){
int minimumCut=end;
for(int start=0; start<=end; start++){
if(palindromeDp[start][end]){
// no cut from position 0 to end
// Otherwise, the min cut will be to add 1 more (start to end) to the previous record for position
// from 0-(start-1)
minimumCut = start==0?0:Math.min(minimumCut, cutsDp[start-1]+1);
}
}
cutsDp[end]=minimumCut;
}
return cutsDp[s.length()-1];
}
public void buildPalindromeDp(String s, int n){
for(int end=0; end<s.length(); end++){
for(int start=0; start<=end; start++){
if(s.charAt(start)==s.charAt(end) && (end-start<=2 || palindromeDp[start+1][end-1])){
palindromeDp[start][end]=true;
}
}
}
}
}
// WRONG, fails "abbab" because it does not go on to check abba for palindrome
// once the palindrome check fails at "ab"
int numPartMin;
HashSet<String> visited;
public int minCut(String s) {
numPartMin = s.length()-1;
visited = new HashSet<>();
helper(s, 0);
return numPartMin;
}
public void helper(String s, int numPart){
System.out.println(s);
if(visited.contains(s)){
return;
}
if(s.length() == 0 || isPalim(s)){
numPartMin = Math.min(numPartMin, numPart);
return;
}
int end=1;
while(end < s.length() && isPalim(s.substring(0, end))){
end++;
}
visited.add(s);
helper(s.substring(end-1), numPart+1);
}
private boolean isPalim(String s){
int start=0;
int end = s.length()-1;
while(start<end){
if(s.charAt(start)!=s.charAt(end)){
return false;
}
start++;
end--;
}
return true;
}Increasing Triplet Subsequence
Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.
Formally the function should:
Return true if there exists i, j, k
such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.
Note: Your algorithm should run in O(n) time complexity and O(1) space complexity.
Example 1:
Input: [1,2,3,4,5]
Output: trueExample 2:
Input: [5,4,3,2,1]
Output: false
- If the current number is bigger than the secondSmallest, we know for sure that we have seen 3 increasing subsequence hence we can immediately return true.
- If the current number is between smallest and secondSmallest, then we need to update secondSmallest since that is no longer valid.
- If current number is smaller than smallest variable, then it means current smallest value is no longer valid. Hence we need to update it. We do not need to update secondSmallest because we know for sure that the current number is smaller than secondSmallest variable since we passed the first if.
- We do not update secondSmallest to hold the value of the previous smallest value (the one we just updated) because the ordering should be that smallest variable has lower index than secondSmallest. In this case, if we update as seen in line 17, the index of the number in the secondSmallest variable is smaller than that in smallest variable, which is wrong. We want secondSmallest variable to hold the value with a greater index than the value in smallest variable.
- At this point, one question that comes to mind is that when in the third if loop if we only update the variable smallest, then wouldnt the ordering be wrong as well. Since we updated secondSmallest before we updated smallest variable, this means the index of secondSmallest value is smaller than index of smallest value. Then, you might try to do the screenshot below.
- But it doesnt work as well. It fails the test case here:
- The reason why it fails is because when we reach the -1, we update smallest = -1, secondSmallest = Integer.MAX_VALUE. Then we lost the [0,2,3] increasing subsequence since when we reach 3, we see that 3 is smaller than secondSmallest variable which holds max value and then we wrongly return False. In this case, perhaps the ordering does not matter much. As long as we know for sure that the secondSmallest variable contains a value that is bigger than at least 1 value that comes before it, we don’t have to update it. When we update the smallest variable in the 3rd If, we are simply making the smallest variable smaller but the two variables no longer contain the values of the increasing subsequence.
Leetcode explanation
Another failed attempt. The solution here is logically correct but has time limit exceeded error.
class Solution {
public boolean increasingTriplet(int[] nums) {
int[] dp = new int[nums.length];
for(int n=0; n<nums.length; n++){
dp[n]=1;
for(int k=n-1; k>=0; k--){
if(nums[n]>nums[k]){
dp[n] = Math.max(dp[n], dp[k]+1);
if(dp[n] == 3) return true;
}
}
}
return false;
}
}Letter Combinations of a phone number
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.
A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
Example 1:
Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]Example 2:
Input: digits = ""
Output: []Example 3:
Input: digits = "2"
Output: ["a","b","c"]
The idea is to make use of recursion to keep trying out all possible combinations of strings. The variable position indicate which index of the input string digits we are currently at. Each iteration is concerned with appending the given String variable curr , accumulated from previous iterations with a single character String. This single character String is the possible value that the position might represent (as we initialised in the HashMap).
When we have tried out all possible combinations, we will add the final string into the global list.
Leet Code 153. Find Minimum in Rotated Sorted Array
Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:
[4,5,6,7,0,1,2]if it was rotated4times.[0,1,2,4,5,6,7]if it was rotated7times.
Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].
Given the sorted rotated array nums, return the minimum element of this array.
Example 1:
Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.Example 2:
Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.Example 3:
Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times.The big idea is to look at the pattern and figure out where exactly could the smallest value be located, when we are at the mid point of the array.
Leetcode explanation
A very cool way of solving this problem is using the Binary Search algorithm. In binary search we find out the mid point and decide to either search on the left or right depending on some condition.
Since the given array is sorted, we can make use of binary search. However, the array is rotated. So simply applying the binary search won’t work here.
In this question we would essentially apply a modified version of binary search where the condition that decides the search direction would be different than in a standard binary search.
// Another possible solution
class Solution {
public int findMin(int[] nums) {
int low = 0;
int high = nums.length-1;
while(low<high){
int mid = (low+high)/2;
if(nums[mid]<nums[high]){
high=mid;
} else {
low=mid+1;
}
}
return nums[high];
}
}
// This solution works for 153 and 154...
class Solution {
public:
int findMin(vector<int>& nums) {
int lo = 0, hi = nums.size() - 1;
int best = -1;
while (lo <= hi) { // always the same cond
int mid = lo + (hi - lo) / 2; // always the same cond
if (nums[mid] > nums[hi]) {
lo = mid+1; // For sure, min is in range [mid+1, hi]
} else {
hi = hi-1;
best=mid; // might be best but not sure., may have better options on the right...try [slow, high-1]
}
}
return nums[best];
}
};Leet Code 154. Find Minimum in Rotated Sorted Array II
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
Find the minimum element.
The array may contain duplicates.
Example 1:
Input: [1,3,5]
Output: 1Example 2:
Input: [2,2,2,0,1]
Output: 0class Solution {
public:
int findMin(vector<int>& nums) {
int lo = 0, hi = nums.size() - 1;
int best = -1;
while (lo <= hi) { // always the same cond
int mid = lo + (hi - lo) / 2; // always the same cond
if (nums[mid] > nums[hi]) {
lo = mid+1; // For sure, min is in range [mid+1, hi]
} else {
hi = hi-1;
best=mid; // might be best but not sure., may have better options on the right...try [slow, high-1]
}
}
return nums[best];
}
}; // also works for 153...0 rotation
/
/
/
/
/
1 rotation
/
/^ if mid is here, for sure min is on the right. so we just shift the whole range.
/
/
/
/
/
/^
/ if mid is here, num[mid]<num[high], for sure min value is current
mid or on the left. So, we just high-- by 1 position.
2 rotations -> the last 2 elements in the prev arr moved to front
f /
e /
d /
c / (same structure)
b /^
a /^
i /
h /
g /
3 rotations -> Last 6 elements moved to front
f /
e /
d /
c / not moved. (same structure)
b / not moved
a / not moved
i /
h /
g /
We see that no matter how many rotations, the structure is always the same.
Hence the algorithm works. (I think i am correct)
The alphabets helps in identifying the /Leet Code 33. Search in Rotated Sorted Array
You are given an integer array nums sorted in ascending order, and an integer target.
Suppose that nums is rotated at some pivot unknown to you beforehand (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
If target is found in the array return its index, otherwise, return -1.
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1Example 3:
Input: nums = [1], target = 0
Output: -1
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;
}
}
Leet Code 4. Median of Two Sorted Arrays
Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.
Follow up: The overall run time complexity should be O(log (m+n)).
Example 1:
Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.Example 2:
Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.Example 3:
Input: nums1 = [0,0], nums2 = [0,0]
Output: 0.00000Example 4:
Input: nums1 = [], nums2 = [1]
Output: 1.00000Example 5:
Input: nums1 = [2], nums2 = []
Output: 2.00000This question is hard…
- We want nums1 to contain the shorter array and nums2 to contain the longer array.
- We then do modified binary search on this smaller array.
- cut1 variable contains the number of elements in nums1 to the left of the cut made on num1 array. The first time we do, (0+len1)/2. In the array with 5 elements, it will be (0+5)/2 = 2.5 = 2. The first cut is after the second element at index 1.
- cut2 variable contains the number of elements in nums2 to the left of the cut made on num2 array. We calculate this from cut1 variable. Note that we want the cut to be at the median position. Median should be at half the length of the total len of the two arrays combined. For eg if we calculate median to be of length X, then since we previously calculated num1 to be contributing cut1 number to the left side of this median point, then num2 will contribute X-cut1 number of elements to the left side of this median point. Hence, we have X-num1 where X=(len+1)/2. The reason why it is (len+1) is so that if the total length of array is odd number, we want the left side of median to contain 1 more element than right side of the median.
- cut1==0 // no elements on left
- cut1==len1 // no elements on right
- With the cut determined, we then make sure that the condition holds
l1<r2 and l2<r1 - If this condition is violated (detected by the IF ELSE loops), then we need to modify the binary search low and high values in num1 array.
- If this condition is not violated, then we have reached the end and can return the median value.
Leet Code 7 Reverse Integer
Given a 32-bit signed integer, reverse digits of an integer.
Note:
Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.
Example 1:
Input: x = 123
Output: 321Example 2:
Input: x = -123
Output: -321Example 3:
Input: x = 120
Output: 21Example 4:
Input: x = 0
Output: 0
Leet Code 88. Merge Sorted Array
Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
Note:
- The number of elements initialized in nums1 and nums2 are m and n respectively.
- You may assume that nums1 has enough space (size that is equal to m + n) to hold additional elements from nums2.
Example:
Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3Output: [1,2,2,3,5,6]
Leet Code 30. Substring with Concatenation of All Words
You are given a string s and an array of strings words of the same length. Return all starting indices of substring(s) in s that is a concatenation of each word in words exactly once, in any order, and without any intervening characters.
You can return the answer in any order.
Example 1:
Input: s = "barfoothefoobarman", words = ["foo","bar"]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are "barfoo" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.Example 2:
Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
Output: []Example 3:
Input: s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
Output: [6,9,12]
Leet Code 31. Next Permutation
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such an arrangement is not possible, it must rearrange it as the lowest possible order (i.e., sorted in ascending order).
The replacement must be in place and use only constant extra memory.
Example 1:
Input: nums = [1,2,3]
Output: [1,3,2]Example 2:
Input: nums = [3,2,1]
Output: [1,2,3]Example 3:
Input: nums = [1,1,5]
Output: [1,5,1]Example 4:
Input: nums = [1]
Output: [1]This question is quite hard. Need to spot the pattern.
Leet code given solution:
First, we observe that a sequence in descending order has no next larger permutation.
We need to find the first pair of two successive numbers a[i]and a[i-1], from the right, which satisfy a[i-1] < a[i]. For eg, 36XXX where 6 is larger than 3. Now, no rearrangements to the right of a[i-1] (section XXX)can create a larger permutation since that subarray consists of numbers in descending order.
We want to create the permutation just larger than the current one. Therefore, we need to replace the number a[i-1] with the number which is just larger than itself among the numbers lying to its right section, say a[j], one of x.
We swap the numbers a[i-1] and a[j]. We now have the correct number at index i-1. But still the current permutation isn’t the permutation that we are looking for. We need the smallest permutation that can be formed by using the numbers only to the right of a[i-1]. Therefore, we need to place those numbers in ascending order to get their smallest permutation. Therefore, we simply need to reverse the numbers following a[i-1] to get the next smallest lexicographic permutation.
class Solution {
public void nextPermutation(int[] nums) {
int i = nums.length - 2;
while(i>=0 && nums[i+1]<=nums[i]){
i--;
}
if(i>=0){
// current i is the index where nums[i] < nums[i+1]
int j = nums.length-1;
// from right to left, get the first number smaller than nums[i]
while(j>=i && nums[j]<=nums[i]){
j--;
}
swap(nums, i, j);
}
reverse(nums, i+1);
}
private void reverse(int[] nums, int start){
int i = start, j = nums.length-1;
while(i<j){
swap(nums, i, j);
j--;
i++;
}
}
private void swap(int[] nums, int i, int j){
int temp = nums[i];
nums[i]=nums[j];
nums[j]=temp;
}
}Leet Code 35. Search Insert Position
Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
Example 1:
Input: nums = [1,3,5,6], target = 5
Output: 2Example 2:
Input: nums = [1,3,5,6], target = 2
Output: 1Example 3:
Input: nums = [1,3,5,6], target = 7
Output: 4Example 4:
Input: nums = [1,3,5,6], target = 0
Output: 0Example 5:
Input: nums = [1], target = 0
Output: 0
Leet Code 36 Valid Sudoku
Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:
- Each row must contain the digits
1-9without repetition. - Each column must contain the digits
1-9without repetition. - Each of the nine
3 x 3sub-boxes of the grid must contain the digits1-9without repetition.
Note:
- A Sudoku board (partially filled) could be valid but is not necessarily solvable.
- Only the filled cells need to be validated according to the mentioned rules.
Leet Code Solution:
One could use
box_index = (row / 3) * 3 + col / 3where/is an integer division,rowis a row number, andcolis a column number.
class Solution {
public boolean isValidSudoku(char[][] board) {
HashSet<Integer> [] rows = new HashSet[9];
HashSet<Integer> [] columns = new HashSet[9];
HashSet<Integer> [] boxes = new HashSet[9];
for(int i=0; i<9; i++){
rows[i]=new HashSet<Integer>();
columns[i]=new HashSet<Integer>();
boxes[i]=new HashSet<Integer>();
}
for(int i=0; i<9; i++){
for(int j=0; j<9; j++){
char num = board[i][j];
if(num != '.'){
int n = (int)num;
int boxIndex = (i/3)*3+j/3; // How to get this formula?
if(rows[i].contains(n) || columns[j].contains(n) || boxes[boxIndex].contains(n)) return false;
rows[i].add(n);
columns[j].add(n);
boxes[boxIndex].add(n);
}
}
}
return true;
}
}The expression (i/3) represents the index of the row block that the cell belongs to. There are three row blocks in a Sudoku puzzle, each containing three rows.
The expression (j/3) represents the index of the column block that the cell belongs to. There are three column blocks in a Sudoku puzzle, each containing three columns.
The expression (i/3)*3 maps the row block index to the starting row index of the block. Each row block contains three rows. So, to get the index of the first row of the block, we need to multiply the row block index by 3. For example, if i=4, then (i/3)*3=3, which is the index of the first row of the second row block. If i=5, then (i/3)*3=3, which is again the index of the first row of the second row block.
Without the multiplication by 3, the formula (i/3) would give us the index of the row block, but not the index of the first row of the block. By multiplying by 3, we shift the index to the first row of the block.
41. First Missing Positive (Hard)
Given an unsorted integer array nums, find the smallest missing positive integer.
Follow up: Could you implement an algorithm that runs in O(n) time and uses constant extra space.?
Example 1:
Input: nums = [1,2,0]
Output: 3Example 2:
Input: nums = [3,4,-1,1]
Output: 2Example 3:
Input: nums = [7,8,9,11,12]
Output: 1
class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
// Base case.
int contains = 0;
for (int i = 0; i < n; i++)
if (nums[i] == 1) {
contains++;
break;
}
if (contains == 0)
return 1;
// Replace negative numbers, zeros,
// and numbers larger than n by 1s.
// After this convertion nums will contain
// only positive numbers.
for (int i = 0; i < n; i++)
if ((nums[i] <= 0) || (nums[i] > n))
nums[i] = 1;
// Use index as a hash key and number sign as a presence detector.
// For example, if nums[1] is negative that means that number `1`
// is present in the array.
// If nums[2] is positive - number 2 is missing.
for (int i = 0; i < n; i++) {
int a = Math.abs(nums[i]);
// If you meet number a in the array - change the sign of a-th element.
// Be careful with duplicates : do it only once.
if (a == n)
nums[0] = - Math.abs(nums[0]);
else
nums[a] = - Math.abs(nums[a]);
}
// Now the index of the first positive number
// is equal to first missing positive.
for (int i = 1; i < n; i++) {
if (nums[i] > 0)
return i;
}
if (nums[0] > 0)
return n;
return n + 1;
}
}O(N) time complexity.
218. The Skyline Problem
A city’s skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Given the locations and heights of all the buildings, return the skyline formed by these buildings collectively.
The geometric information of each building is given in the array buildings where buildings[i] = [lefti, righti, heighti]:
leftiis the x coordinate of the left edge of theithbuilding.rightiis the x coordinate of the right edge of theithbuilding.heightiis the height of theithbuilding.
You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.
The skyline should be represented as a list of “key points” sorted by their x-coordinate in the form [[x1,y1],[x2,y2],...]. Each key point is the left endpoint of some horizontal segment in the skyline except the last point in the list, which always has a y-coordinate 0 and is used to mark the skyline's termination where the rightmost building ends. Any ground between the leftmost and rightmost buildings should be part of the skyline's contour.
Note: There must be no consecutive horizontal lines of equal height in the output skyline. For instance, [...,[2 3],[4 5],[7 5],[11 5],[12 7],...] is not acceptable; the three lines of height 5 should be merged into one in the final output as such: [...,[2 3],[4 5],[12 7],...]
Example 1:
Input: buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
Output: [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]
Explanation:
Figure A shows the buildings of the input.
Figure B shows the skyline formed by those buildings. The red points in figure B represent the key points in the output list.Example 2:
Input: buildings = [[0,2,3],[2,5,3]]
Output: [[0,3],[5,0]]Leet Code Solution:
Copied from a YouTube tutorial on this question.
The idea is to maintain 2 data structures: (1) TreeMap where the key indicates the X-Coord, Value is an ArrayList of int array of values (start, end, height). This array list of int arrays are buildings that start with the key X Coord. (2) Max Heap which contains the height of all the buildings. As we iterate through the Tree Map, we will update this Max Heap. At any point, the max heap will contain the heights of all the buildings presently at the key value (X-Coord) we are iterating at in the Tree Map.
class Solution {
public List<List<Integer>> getSkyline(int[][] buildings) {
// TreeMap: Key: X-coord. Value: ArrayList of Int values
// Max heap: height of all buildings
TreeMap<Integer, List<int[]>> map = new TreeMap<>();
for(int[] build: buildings){
map.putIfAbsent(build[0], new ArrayList<>());
map.putIfAbsent(build[1], new ArrayList<>());
map.get(build[0]).add(build);
map.get(build[1]).add(build);
}
PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> b[2]-a[2]);
List<List<Integer>> results = new ArrayList<>();
for(int xCoord: map.keySet()){
List<int[]> bs = map.get(xCoord);
for(int[] b: bs){
if(b[0] == xCoord){
// start point
maxHeap.offer(b);
} else {
// end point
maxHeap.remove(b);
}
}
if (maxHeap.size()==0){
List<Integer> temp = new ArrayList<>();
temp.add(xCoord);
temp.add(0);
results.add(temp);
} else {
int maxHeight = maxHeap.peek()[2];
if(results.size()==0 || results.get(results.size()-1).get(1) != maxHeight){
List<Integer> temp = new ArrayList<>();
temp.add(xCoord);
temp.add(maxHeight);
results.add(temp);
}
}
}
return results;
}
}807. Max Increase to Keep City Skyline
There is a city composed of n x n blocks, where each block contains a single building shaped like a vertical square prism. You are given a 0-indexed n x n integer matrix grid where grid[r][c] represents the height of the building located in the block at row r and column c.
A city’s skyline is the outer contour formed by all the building when viewing the side of the city from a distance. The skyline from each cardinal direction north, east, south, and west may be different.
We are allowed to increase the height of any number of buildings by any amount (the amount can be different per building). The height of a 0-height building can also be increased. However, increasing the height of a building should not affect the city's skyline from any cardinal direction.
Return the maximum total sum that the height of the buildings can be increased by without changing the city’s skyline from any cardinal direction.
Example 1:
Input: grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]
Output: 35
Explanation: The building heights are shown in the center of the above image.
The skylines when viewed from each cardinal direction are drawn in red.
The grid after increasing the height of buildings without affecting skylines is:
gridNew = [ [8, 4, 8, 7],
[7, 4, 7, 7],
[9, 4, 8, 7],
[3, 3, 3, 3] ]Example 2:
Input: grid = [[0,0,0],[0,0,0],[0,0,0]]
Output: 0
Explanation: Increasing the height of any building will result in the skyline changing.class Solution {
public int maxIncreaseKeepingSkyline(int[][] grid) {
// as long as it is not the max in its col or row, we can increase it
int[] row = new int[grid.length];
int[] col = new int[grid[0].length];
for(int i=0; i<grid.length; i++){
for(int j=0; j<grid[0].length; j++){
row[i]=Math.max(row[i], grid[i][j]);
col[j]=Math.max(col[j], grid[i][j]);
}
}
int val = 0;
for(int i=0; i<grid.length; i++){
for(int j=0; j<grid[0].length; j++){
if(grid[i][j]<row[i] && grid[i][j]<col[j]){
val += Math.min(row[i], col[j])-grid[i][j];
}
}
}
return val;
}
}Leet Code 295. Find Median from Data Stream
Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.
For example,
[2,3,4], the median is 3
[2,3], the median is (2 + 3) / 2 = 2.5
Design a data structure that supports the following two operations:
- void addNum(int num) — Add a integer number from the data stream to the data structure.
- double findMedian() — Return the median of all elements so far
480. Sliding Window Median
The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle values.
- For examples, if
arr = [2,3,4], the median is3. - For examples, if
arr = [1,2,3,4], the median is(2 + 3) / 2 = 2.5.
You are given an integer array nums and an integer k. There is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.
Return the median array for each window in the original array. Answers within 10-5 of the actual value will be accepted.
Example 1:
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [1.00000,-1.00000,-1.00000,3.00000,5.00000,6.00000]
Explanation:
Window position Median
--------------- -----
[1 3 -1] -3 5 3 6 7 1
1 [3 -1 -3] 5 3 6 7 -1
1 3 [-1 -3 5] 3 6 7 -1
1 3 -1 [-3 5 3] 6 7 3
1 3 -1 -3 [5 3 6] 7 5
1 3 -1 -3 5 [3 6 7] 6Example 2:
Input: nums = [1,2,3,4,2,3,1,4,2], k = 3
Output: [2.00000,3.00000,3.00000,3.00000,2.00000,3.00000,2.00000]class Solution {
PriorityQueue<Integer> maxHeap; // 1st part
PriorityQueue<Integer> minHeap; // 2nd part
public Solution() {
// use Collections.reverseOrder() as comparator as this will work when input number as max integer, can't use (a,b)->b-a
maxHeap = new PriorityQueue<>(Collections.reverseOrder());
minHeap = new PriorityQueue<>();
}
void addNum(int n) {
if(maxHeap.size()==0 || n <= maxHeap.peek()) {
maxHeap.offer(n);
} else {
minHeap.offer(n);
}
rebalance();
}
void remove(int num) {
if(num <= maxHeap.peek()) maxHeap.remove(num);
else minHeap.remove(num);
rebalance();
}
void rebalance() {
if(minHeap.size() > maxHeap.size()) maxHeap.offer(minHeap.poll());
// max heap can have one extra node than min heap, as we will use for returning the median when total input size is odd number
else if(maxHeap.size() > minHeap.size() + 1) minHeap.offer(maxHeap.poll());
}
double findMedian() {
if(maxHeap.size() == minHeap.size()) return maxHeap.peek()/2.0 + minHeap.peek() /2.0;
else return maxHeap.peek();
}
public double[] medianSlidingWindow(int[] nums, int k) {
int start = 0;
double[] result = new double[nums.length - k + 1 ];
for(int end=0; end < nums.length; end++) {
addNum(nums[end]);
if(end + 1 >= k) {// shrink the window & calculate the median
result[start] = findMedian();
remove(nums[start]); // remove the start number as we move forward the next window size
start++; // move start window ahead
}
}
return result;
}
}2387. Median of a Row Wise Sorted Matrix
Given an m x n matrix grid containing an odd number of integers where each row is sorted in non-decreasing order, return the median of the matrix.
You must solve the problem in less than O(m * n) time complexity.
Example 1:
Input: grid = [[1,1,2],[2,3,3],[1,3,4]]
Output: 2
Explanation: The elements of the matrix in sorted order are 1,1,1,2,2,3,3,3,4. The median is 2.Example 2:
Input: grid = [[1,1,3,3,4]]
Output: 3
Explanation: The elements of the matrix in sorted order are 1,1,3,3,4. The median is 3.class Solution {
public int matrixMedian(int[][] grid) {
int m=grid.length;
int n=grid[0].length;
int low=0;
int high = (int)Math.pow(10, 6)+1;
while(low<high){
int mid = low + (high-low) / 2;
if(fulfill(mid, grid)){
high = mid; // try and see if can go lower...
} else {
low = mid + 1;
}
}
return high;
}
// returns true if the number of elements that are <= s is n*m/2+1.
// Half the numbers in the grid is greater or equal to s.
public boolean fulfill(int s, int[][] grid){
int res = 0;
for(int[] row: grid){
res+=bisectRight(row, s);
}
return res >= (grid.length * grid[0].length) / 2 + 1;
}
public int bisectRight(int[] row, int target){
int index = Arrays.binarySearch(row, target);
if (index < 0) {
index = -(index + 1);
} else {
// If the target element is found, move to the next index
// We need to get the rightmost index if there are multiple
// similar values
while (index < row.length && row[index] == target) {
index++;
}
}
return index;
}
}Leet Code 249. Group Shifted Strings (Medium)
Given a string, we can “shift” each of its letter to its successive letter, for example: "abc" -> "bcd". We can keep "shifting" which forms the sequence:
"abc" -> "bcd" -> ... -> "xyz"Given a list of strings which contains only lowercase alphabets, group all strings that belong to the same shifting sequence.
For example, given: ["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"],
A solution is:
[
["abc","bcd","xyz"],
["az","ba"],
["acef"],
["a","z"]
]Two strings are considered to be in the same group if we can shift those strings and get to the same string. The idea to solve this question is to compute the difference between each character in a string, then store them in a stack. For eg, if i have a word “abe” then the stack will contain [1,3]. We have a global hash map where the key would be the stack of integers and the values would be a list of string that has this key stack.
Note that we have to check if the difference is smaller than 0 and add 26 to it. This is because we need to account for wrapping…
Below is a tried and tested code.
class Solution {
public List<List<String>> groupStrings(String[] strings) {
List<List<String>> result = new LinkedList<>();
Map<String, List<String>> map = new HashMap<>();
for(String str: strings){
String diffString = "";
for(int i=1; i<str.length(); i++){
int newDiff = Character.getNumericValue(str.charAt(i)) - Character.getNumericValue(str.charAt(i-1));
if(newDiff<0){
newDiff+=26;
}
diffString += "#" + newDiff;
}
map.putIfAbsent(diffString, new ArrayList<>());
map.get(diffString).add(str);
}
for(List<String> each: map.values()){
result.add(each);
}
return result;
}
}Leet Code 76. Minimum Window Substring (Hard)
Given two strings s and t, return the minimum window in s which will contain all the characters in t. If there is no such window in s that covers all characters in t, return the empty string "".
Note that If there is such a window, it is guaranteed that there will always be only one unique minimum window in s.
Example 1:
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"Example 2:
Input: s = "a", t = "a"
Output: "a"
This is the sliding window method.
345. Reverse Vowels of a String
Write a function that takes a string as input and reverse only the vowels of a string.
Example 1:
Input: "hello"
Output: "holle"Example 2:
Input: "leetcode"
Output: "leotcede"
// Or this...
class Solution {
public String reverseVowels(String s) {
HashSet<Character> set = new HashSet<>();
set.add('a');
set.add('e');
set.add('i');
set.add('o');
set.add('u');
set.add('A');
set.add('E');
set.add('I');
set.add('O');
set.add('U');
String reversed = "";
for(int i=0; i<s.length(); i++){
if(set.contains(s.charAt(i))){
reversed = s.substring(i, i+1) + reversed;
}
}
System.out.println(reversed);
int index = 0;
for(int i=0; i<s.length(); i++){
if(set.contains(s.charAt(i))){
String end = "";
if(index+1 < s.length()){
end = s.substring(i+1);
}
s = s.substring(0, i)+reversed.substring(index, index+1)+ end;
index++;
}
}
return s;
}
}Leet Code 829. Consecutive Numbers Sum
Given a positive integer N, how many ways can we write it as a sum of consecutive positive integers?
Example 1:
Input: 5
Output: 2
Explanation: 5 = 5 = 2 + 3Example 2:
Input: 9
Output: 3
Explanation: 9 = 9 = 4 + 5 = 2 + 3 + 4Example 3:
Input: 15
Output: 4
Explanation: 15 = 15 = 8 + 7 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5Using prefix sum method works for some of the test cases but fails for others when the number gets big. This is due to Integer overflow. Nevertheless, i will still put my attempt.
The correct Solution: Too complicated to understand, seriously….TODO
151. Reverse Words in a String
Given an input string s, reverse the order of the words.
A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.
Return a string of the words in reverse order concatenated by a single space.
Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.
Example 1:
Input: s = "the sky is blue"
Output: "blue is sky the"Example 2:
Input: s = " hello world "
Output: "world hello"
Explanation: Your reversed string should not contain leading or trailing spaces.Example 3:
Input: s = "a good example"
Output: "example good a"
Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.Example 4:
Input: s = " Bob Loves Alice "
Output: "Alice Loves Bob"Example 5:
Input: s = "Alice does not even like bob"
Output: "bob like even not does Alice"The idea is to reverse the given string. Then, for each word segment separated by space, we reverse the word.
Since the given string might have spacing (extra) between words or outside of the sentence, we need to remove them.
class Solution {
public String reverseWords(String s) {
String trimmed = s.trim();
String[] splitWord = trimmed.split(" ");
String result = "";
for(int i=splitWord.length-1; i>=0; i--){
if(splitWord[i].isEmpty()) continue;
result+=splitWord[i].trim()+" ";
}
return result.trim();
}
}186. Reverse Words in a String II
Given a character array s, reverse the order of the words.
A word is defined as a sequence of non-space characters. The words in s will be separated by a single space.
Your code must solve the problem in-place, i.e. without allocating extra space.
Example 1:
Input: s = ["t","h","e"," ","s","k","y"," ","i","s"," ","b","l","u","e"]
Output: ["b","l","u","e"," ","i","s"," ","s","k","y"," ","t","h","e"]Example 2:
Input: s = ["a"]
Output: ["a"]class Solution {
public void reverseWords(char[] s) {
reverse(s, 0, s.length-1);
int start=0;
while(start<s.length){
int end = start;
while(end<s.length && s[end] != ' '){
end++;
}
reverse(s, start, end-1);
start = end+1;
}
}
private void reverse (char[] s, int start, int end){
while(start<end){
char tmp = s[start];
s[start]=s[end];
s[end]=tmp;
start++;
end--;
}
}
}The idea is to reverse the entire string first, then reverse each individual word.
209. 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.
Sort of like sliding window.
The thing to note is line 18. We compute the length to be end — start instead of (end-start+1), this is because the end index would be incremented by 1 and then it fails the while condition. This means the end index is not valid/not included in making the sum.
Below is a brute force solution . Think about it, we don’t actually need to keep recomputing sum…so we should follow up to improve this algorithm using sliding window and storing a sum counter.
for(int i=0; i<nums.length; i++){
int j=i;
int sum = 0;
while(sum<target && j<nums.length){
sum+=nums[j];
j++;
}
if(sum>=target){
minLength = Math.min(minLength, j-i);
}
}1679. Max Number of K-Sum Pairs
You are given an integer array nums and an integer k.
In one operation, you can pick two numbers from the array whose sum equals k and remove them from the array.
Return the maximum number of operations you can perform on the array.
Example 1:
Input: nums = [1,2,3,4], k = 5
Output: 2
Explanation: Starting with nums = [1,2,3,4]:
- Remove numbers 1 and 4, then nums = [2,3]
- Remove numbers 2 and 3, then nums = []
There are no more pairs that sum up to 5, hence a total of 2 operations.Example 2:
Input: nums = [3,1,3,4,3], k = 6
Output: 1
Explanation: Starting with nums = [3,1,3,4,3]:
- Remove the first two 3's, then nums = [1,4,3]
There are no more pairs that sum up to 6, hence a total of 1 operation.
This question is just finding the number of pairs that adds up to k. Even though they have “max”, it is not really a DP question…because the ordering of the selecting pairs, considering numbers in the arr does not matter.
348. Design Tic-Tac-Toe
Design a Tic-tac-toe game that is played between two players on a nxn grid.
You may assume the following rules:
- A move is guaranteed to be valid and is placed on an empty block.
- Once a winning condition is reached, no more moves is allowed.
- A player who succeeds in placing n of their marks in a horizontal, vertical, or diagonal row wins the game.
The O(n²) algorithm is pretty easy to derive….but can we do better?
// Correct solution that passes all TCs
class TicTacToe {
int[][] board;
public TicTacToe(int n) {
board = new int[n][n];
}
public int move(int row, int col, int player) {
board[row][col]=player;
return getWinner(row, col, player);
}
// For every move, check if the row/col contains any winner
public int getWinner(int row, int col, int player){
// check entire row
int countRow=0;
for(int i=0; i<board.length; i++){
if(board[row][i] == player){
countRow ++;
} else {
break;
}
}
if(countRow == board.length) return player;
// check entire col
int countCol=0;
for(int i=0; i<board.length; i++){
if(board[i][col] == player){
countCol ++;
} else {
break;
}
}
if(countCol == board.length) return player;
// LEFT TO RIGHT DIAGONAL
// check upp diagonal
int i = row;
int j = col;
int countUppDiag = 0;
while(i >= 0 && j >= 0){
if(board[i][j] == player){
countUppDiag ++;
} else {
break;
}
i--;
j--;
}
// check bottom diagonal
int i2 = row+1;
int j2 = col+1;
int countBotDiag = 0;
while(i2 < board.length && j2 < board.length){
if(board[i2][j2] == player){
countBotDiag ++;
} else {
break;
}
i2++;
j2++;
}
if((countBotDiag+countUppDiag) == board.length) return player;
// RIGHT TO LEFT INFLATION
// check upp diagonal
int i3 = row;
int j3 = col;
int countUppDiagRight = 0;
while(i3 >= 0 && j3 <board.length){
if(board[i3][j3] == player){
countUppDiagRight ++;
} else {
break;
}
i3--;
j3++;
}
// check bottom diagonal
int i4 = row+1;
int j4 = col-1;
int countBotDiagRight = 0;
while(i4 < board.length && j4 >=0){
if(board[i4][j4] == player){
countBotDiagRight ++;
} else {
break;
}
i4++;
j4--;
}
if((countUppDiagRight+countBotDiagRight) == board.length) return player;
return 0;
}
}
/**
* Your TicTacToe object will be instantiated and called as such:
* TicTacToe obj = new TicTacToe(n);
* int param_1 = obj.move(row,col,player);
*/1498. Number of Subsequences That Satisfy the Given Sum Condition
Given an array of integers nums and an integer target.
Return the number of non-empty subsequences of nums such that the sum of the minimum and maximum element on it is less or equal to target. Since the answer may be too large, return it modulo 109 + 7.
Example 1:
Input: nums = [3,5,6,7], target = 9
Output: 4
Explanation: There are 4 subsequences that satisfy the condition.
[3] -> Min value + max value <= target (3 + 3 <= 9)
[3,5] -> (3 + 5 <= 9)
[3,5,6] -> (3 + 6 <= 9)
[3,6] -> (3 + 6 <= 9)Example 2:
Input: nums = [3,3,6,8], target = 10
Output: 6
Explanation: There are 6 subsequences that satisfy the condition. (nums can have repeated numbers).
[3] , [3] , [3,3], [3,6] , [3,6] , [3,3,6]Example 3:
Input: nums = [2,3,3,4,6,7], target = 12
Output: 61
Explanation: There are 63 non-empty subsequences, two of them don't satisfy the condition ([6,7], [7]).
Number of valid subsequences (63 - 2 = 61).Example 4:
Input: nums = [5,2,4,1,7,6,8], target = 16
Output: 127
Explanation: All non-empty subset satisfy the condition (2^7 - 1) = 127Leetcode answer: Binary search
Intuition
Starting from the brute-force approach, if we simply generate all possible subsequences and then iterate through each subsequence to find its maximum and minimum elements, this approach is feasible but the time complexity will be very high.
Assuming the size of the array is n, we will have O(2^n) non-empty subsequences, resulting in a time complexity of O(2^n.n). This method is very expensive and indicates that we need a more efficient way to traverse the subsequence.
Note that we only need to consider the minimum and maximum elements of a subsequence to determine whether it is valid, and elements with values between them do not affect our judgment. Therefore, we can traverse all possible (minimum, maximum) combinations and check if they are valid.
If there are k subsequences with min as the minimum value and max as the maximum value, we only need to check if min + max <= target. The number of such subsequences k depends on how many elements have values that are between min and max. Therefore, we need to sort nums first, so that the number of values between min and max can be represented by their index difference.
Here, we let left and right be the pointers to the minimum element and the maximum element. That is nums[left] = min.
Now we need to traverse each possible minimum value. For min = nums[left], we need to ensure that the subsequences with this number as the minimum value are valid, which means the maximum element of these subsequences cannot be greater than target-nums[left]. In other words, we need to find the largest element that is not greater than target-nums[left]. As shown in the picture below, we have found that nums[right] = 12 is the rightmost element that is smaller than or equal to 17 - nums[left], then we can freely pick elements within the range [left + 1, right] to make valid subsequences.
Since the array is already sorted, we can use binary search to find the insertion position of target - nums[left]. Note that we are looking for the rightmost element that is smaller than or equal to target - nums[left], and the binary search finds the index of the smallest element that is larger than target - nums[left]. Therefore, once we find the rightmost insertion position as k, we have right = k - 1.
Now we have the left and right indices left and right. For each number in the range [left + 1, right], there are 2 options: we can either take it or not take it, so there are a total of 2^(right - left) valid subsequences that have nums[left] as the minimum element.
Next, we move to the next min by moving the left pointer left one step to the right. We repeat the process by using binary search to find the new insertion position of target - nums[left].
Sometimes we may encounter situations where left > right and we don't need to consider these subsequences because they have already been calculated before and there is no need to recalculate them again.
Algorithm
- Initialize
answer = 0and the length ofnumsasn. - Iterate over the left index
leftfrom0ton - 1, for each indexleft:
- Use binary search to locate the rightmost index
rightwhichnums[right] <= target - nums[left]. - If
left <= right, count the total number of valid subsequences as 2right - left2 ^ {\text{right - left}}2right - left - Increment
answerby the number of valid subsequences.
3. Return answer once the iteration ends.
class Solution {
public static int binarySearchRightmost(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] <= target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
public int numSubseq(int[] nums, int target) {
int n = nums.length;
int mod = 1_000_000_007;
Arrays.sort(nums);
int[] power = new int[n];
power[0] = 1;
for (int i = 1; i < n; ++i) {
power[i] = (power[i - 1] * 2) % mod;
}
int answer = 0;
// Iterate over each left pointer.
for (int left = 0; left < n; left++) {
// Find the insertion position for `target - nums[left]`
// 'right' equals the insertion index minus 1.
int right = binarySearchRightmost(nums, target - nums[left]) - 1;
if (right >= left) {
answer += power[right - left];
answer %= mod;
}
}
return answer;
}
}The code initializes an integer array named power with n elements. It then sets the first element of the array to 1. The purpose of the code is to generate a sequence of powers of two modulo a given mod value, where mod is an integer. The code achieves this by using a for-loop that iterates from index 1 to n-1 of the array. In each iteration, the code sets the value of power[i] to be twice the previous element in the array power[i-1], but with the result modulo mod.
In other words, the power array will contain the sequence of powers of 2 modulo mod from 2^0 to 2^(n-1). The modulo operation is used to ensure that the result stays within the range of integers that can be represented by the variable type used.
1052. Grumpy Bookstore Owner
Today, the bookstore owner has a store open for customers.length minutes. Every minute, some number of customers (customers[i]) enter the store, and all those customers leave after the end of that minute.
On some minutes, the bookstore owner is grumpy. If the bookstore owner is grumpy on the i-th minute, grumpy[i] = 1, otherwise grumpy[i] = 0. When the bookstore owner is grumpy, the customers of that minute are not satisfied, otherwise they are satisfied.
The bookstore owner knows a secret technique to keep themselves not grumpy for X minutes straight, but can only use it once.
Return the maximum number of customers that can be satisfied throughout the day.
Example 1:
Input: customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3
Output: 16
Explanation: The bookstore owner keeps themselves not grumpy for the last 3 minutes.
The maximum number of customers that can be satisfied = 1 + 1 + 1 + 1 + 7 + 5 = 16.class Solution {
int sum = 0;
for(int i=0; i<customers.length; i++){
if(grumpy[i]==0 || i<minutes){
sum+=customers[i];
}
}
int max = sum;
int start=0;
int end = minutes;
while(end <= customers.length-1){
if(grumpy[end] == 1){
sum+=customers[end];
}
if(grumpy[start]==1){
sum-=customers[start];
}
max = Math.max(max, sum);
end++;
start++;
}
return max;
}1743. Restore the Array From Adjacent Pairs
There is an integer array nums that consists of n unique elements, but you have forgotten it. However, you do remember every pair of adjacent elements in nums.
You are given a 2D integer array adjacentPairs of size n - 1 where each adjacentPairs[i] = [ui, vi] indicates that the elements ui and vi are adjacent in nums.
It is guaranteed that every adjacent pair of elements nums[i] and nums[i+1] will exist in adjacentPairs, either as [nums[i], nums[i+1]] or [nums[i+1], nums[i]]. The pairs can appear in any order.
Return the original array nums. If there are multiple solutions, return any of them.
Example 1:
Input: adjacentPairs = [[2,1],[3,4],[3,2]]
Output: [1,2,3,4]
Explanation: This array has all its adjacent pairs in adjacentPairs.
Notice that adjacentPairs[i] may not be in left-to-right order.Example 2:
Input: adjacentPairs = [[4,-2],[1,4],[-3,1]]
Output: [-2,4,1,-3]
Explanation: There can be negative numbers.
Another solution is [-3,1,4,-2], which would also be accepted.Example 3:
Input: adjacentPairs = [[100000,-100000]]
Output: [100000,-100000]class Solution {
public:
vector<int> restoreArray(vector<vector<int>>& adjacentPairs) {
unordered_map<int, vector<int>> map; // bidirectional connection
for (const auto& pair : adjacentPairs) {
int first = pair[0];
int second = pair[1];
map[first].emplace_back(second); //replace or update
map[second].emplace_back(first);
}
// find the element that only has 1 count. it is either the head or tail.
int root=-1;
for(auto it=map.begin(); it!=map.end(); it++){
if(it->second.size() == 1){
root=it->first;
break;
}
}
set<int> visited;
vector<int> result;
queue<int> q;
q.push(root);
while(q.size()>0){
int curr = q.front();
q.pop();
visited.insert(curr);
result.push_back(curr);
for(int i: map[curr]){
if(visited.count(i)>0){
continue;
}
q.push(i);
}
}
return result;
}
};2024. Maximize the Confusion of an Exam
A teacher is writing a test with n true/false questions, with 'T' denoting true and 'F' denoting false. He wants to confuse the students by maximizing the number of consecutive questions with the same answer (multiple trues or multiple falses in a row).
You are given a string answerKey, where answerKey[i] is the original answer to the ith question. In addition, you are given an integer k, the maximum number of times you may perform the following operation:
- Change the answer key for any question to
'T'or'F'(i.e., setanswerKey[i]to'T'or'F').
Return the maximum number of consecutive 'T's or 'F's in the answer key after performing the operation at most k times.
Example 1:
Input: answerKey = "TTFF", k = 2
Output: 4
Explanation: We can replace both the 'F's with 'T's to make answerKey = "TTTT".
There are four consecutive 'T's.Example 2:
Input: answerKey = "TFFT", k = 1
Output: 3
Explanation: We can replace the first 'T' with an 'F' to make answerKey = "FFFT".
Alternatively, we can replace the second 'T' with an 'F' to make answerKey = "TFFF".
In both cases, there are three consecutive 'F's.Example 3:
Input: answerKey = "TTFTTFTT", k = 1
Output: 5
Explanation: We can replace the first 'F' to make answerKey = "TTTTTFTT"
Alternatively, we can replace the second 'F' to make answerKey = "TTFTTTTT".
In both cases, there are five consecutive 'T's.class Solution {
public int maxConsecutiveAnswers(String answerKey, int k) {
int maxSize = k;
Map<Character, Integer> count = new HashMap<>();
for(int i=0; i<k; i++){
char currCar = answerKey.charAt(i);
count.put(currCar, count.getOrDefault(currCar, 0)+1);
}
int left = 0;
for(int right=k; right<answerKey.length(); right++){
// add right char
char currCar = answerKey.charAt(right);
count.put(currCar, count.getOrDefault(currCar, 0)+1);
while(Math.min(count.getOrDefault('T', 0), count.getOrDefault('F', 0)) > k){
// remove left char
count.put(answerKey.charAt(left), count.get(answerKey.charAt(left)) - 1);
left++;
}
maxSize = Math.max(maxSize, right-left+1); // get count from left to right
}
return maxSize;
}
}
485. Max Consecutive Ones
Given a binary array nums, return the maximum number of consecutive 1's in the array.
Example 1:
Input: nums = [1,1,0,1,1,1]
Output: 3
Explanation: The first two digits or the last three digits are consecutive 1s. The maximum number of consecutive 1s is 3.Example 2:
Input: nums = [1,0,1,1,0,1]
Output: 2Constraints:
1 <= nums.length <= 105nums[i]is either0or1.
class Solution {
public int findMaxConsecutiveOnes(int[] nums) {
int max = 0;
int count = 0;
for(int i=0; i<nums.length; i++){
if(i==0){
if(nums[i]==1){
max=1;
count=1;
}
} else if (nums[i]==1 && nums[i-1]==1){
count++;
} else if (nums[i]==1){
count=1;
}
max=Math.max(count, max);
}
return max;
}
}487. Max Consecutive Ones II
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.Example 2:
Input: nums = [1,0,1,1,0,1]
Output: 4
Explanation:
- If we flip the first zero, nums becomes [1,1,1,1,0,1] and we have 4 consecutive ones.
- If we flip the second zero, nums becomes [1,0,1,1,1,1] and we have 4 consecutive ones.
The max number of consecutive ones is 4.Constraints:
1 <= nums.length <= 105nums[i]is either0or1.
class Solution {
public int findMaxConsecutiveOnes(int[] nums) {
int[] left = new int[nums.length]; // num of 1s to the left excluding itself
for(int i=1; i<nums.length; i++){
if(nums[i-1]==1){
left[i] = left[i-1]+1;
}
}
int[] right = new int[nums.length]; // num of 1s to the right excluding itself
for(int i=nums.length-2; i>=0; i--){
if(nums[i+1]==1){
right[i] = right[i+1]+1;
}
}
int max = 0;
for(int i=0; i<nums.length; i++){
max=Math.max(max, left[i]+right[i]);
}
return max+1; // 1 represents i (nums[i] can be 0 or 1)
}
}Follow up: What if the input numbers come in one by one as an infinite stream? In other words, you can’t store all numbers coming from the stream as it’s too large to hold in memory. Could you solve it efficiently?
Do the sliding window approach
class Solution {
public int findMaxConsecutiveOnes(int[] nums) {
int longestSequence = 0;
int left = 0;
int right = 0;
int numZeroes = 0;
// while our window is in bounds
while (right < nums.length) {
// add the right most element into our window
if (nums[right] == 0) {
numZeroes++;
}
// if our window is invalid, contract our window
while (numZeroes == 2) {
if (nums[left] == 0) {
numZeroes--;
}
left++;
}
// update our longest sequence answer
longestSequence = Math.max(longestSequence, right - left + 1);
// expand our window
right++;
}
return longestSequence;
}
}1004. Max Consecutive Ones III
Given a binary array nums and an integer k, return the maximum number of consecutive 1's in the array if you can flip at most k 0's.
Example 1:
Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output: 6
Explanation: [1,1,1,0,0,1,1,1,1,1,1]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.Example 2:
Input: nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], k = 3
Output: 10
Explanation: [0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.Constraints:
1 <= nums.length <= 105nums[i]is either0or1.0 <= k <= nums.length
Similar to 2024
class Solution {
public int longestOnes(int[] nums, int k) {
int maxSize = k;
Map<Integer, Integer> count = new HashMap<>();
for(int i=0; i<k; i++){
int currCar = nums[i];
count.put(currCar, count.getOrDefault(currCar, 0)+1);
}
int left = 0;
for(int right=k; right<nums.length; right++){
// add right char
int currCar = nums[right];
count.put(currCar, count.getOrDefault(currCar, 0)+1);
while(count.getOrDefault(0, 0) > k){
// remove left char
count.put(nums[left], count.get(nums[left]) - 1);
left++;
}
maxSize = Math.max(maxSize, right-left+1); // get count from left to right
}
return maxSize;
}
}2661. First Completely Painted Row or Column
You are given a 0-indexed integer array arr, and an m x n integer matrix mat. arr and mat both contain all the integers in the range [1, m * n].
Go through each index i in arr starting from index 0 and paint the cell in mat containing the integer arr[i].
Return the smallest index i at which either a row or a column will be completely painted in mat.
Example 1:
Input: arr = [1,3,4,2], mat = [[1,4],[2,3]]
Output: 2
Explanation: The moves are shown in order, and both the first row and second column of the matrix become fully painted at arr[2].Example 2:
Input: arr = [2,8,7,4,1,3,5,6,9], mat = [[3,2,5],[1,4,6],[8,7,9]]
Output: 3
Explanation: The second column becomes fully painted at arr[3].class Solution {
public int firstCompleteIndex(int[] arr, int[][] mat) {
Map<Integer, int[]> map = new HashMap<>();
for(int i=0; i<mat.length; i++){
for(int j=0; j<mat[0].length; j++){
int[] coord = {i, j};
map.put(mat[i][j], coord);
}
}
Map<Integer, Integer> rows = new HashMap<>();
Map<Integer, Integer> cols = new HashMap<>();
for(int i=0; i<arr.length; i++){
int[] coord = map.get(arr[i]);
rows.put(coord[0], rows.getOrDefault(coord[0], 0)+1);
cols.put(coord[1], cols.getOrDefault(coord[1], 0)+1);
if(rows.get(coord[0]) == mat[0].length){
return i;
} else if (cols.get(coord[1]) == mat.length){
return i;
}
}
return 0;
}
// 4,3,5
// 1,2,6
}2483. Minimum Penalty for a Shop
You are given the customer visit log of a shop represented by a 0-indexed string customers consisting only of characters 'N' and 'Y':
- if the
ithcharacter is'Y', it means that customers come at theithhour - whereas
'N'indicates that no customers come at theithhour.
If the shop closes at the jth hour (0 <= j <= n), the penalty is calculated as follows:
- For every hour when the shop is open and no customers come, the penalty increases by
1. - For every hour when the shop is closed and customers come, the penalty increases by
1.
Return the earliest hour at which the shop must be closed to incur a minimum penalty.
Note that if a shop closes at the jth hour, it means the shop is closed at the hour j.
Example 1:
Input: customers = "YYNY"
Output: 2
Explanation:
- Closing the shop at the 0th hour incurs in 1+1+0+1 = 3 penalty.
- Closing the shop at the 1st hour incurs in 0+1+0+1 = 2 penalty.
- Closing the shop at the 2nd hour incurs in 0+0+0+1 = 1 penalty.
- Closing the shop at the 3rd hour incurs in 0+0+1+1 = 2 penalty.
- Closing the shop at the 4th hour incurs in 0+0+1+0 = 1 penalty.
Closing the shop at 2nd or 4th hour gives a minimum penalty. Since 2 is earlier, the optimal closing time is 2.Example 2:
Input: customers = "NNNNN"
Output: 0
Explanation: It is best to close the shop at the 0th hour as no customers arrive.Example 3:
Input: customers = "YYYY"
Output: 4
Explanation: It is best to close the shop at the 4th hour as customers arrive at each hour.Constraints:
1 <= customers.length <= 105customersconsists only of characters'Y'and'N'.
class Solution {
public int bestClosingTime(String customers) {
int currPenalty = 0;
for(int i=0; i<customers.length(); i++){
if(customers.charAt(i) == 'Y'){
currPenalty++;
}
}
int minPenalty = currPenalty; // penalty when shop never open at all
int earliestHour = 0;
for(int i=0; i<customers.length(); i++){
char ch = customers.charAt(i);
if(ch == 'Y'){
currPenalty--; // shop open and cus entered shop, so no penalty
} else {
currPenalty++; // shop open but no cus, so penalty
}
if(currPenalty < minPenalty){
earliestHour = i+1;
minPenalty = currPenalty;
}
}
return earliestHour;
}
}Let nnn be the length of customers.
Time complexity: O(n)
- The first traversal is used to calculate the total count of ‘Y’ in
customers, which takes O(n) time. - In each step of the second traversal, we update
cur_penalty,min_penalty, andearliest_hourbased on the charactercustomers[i], which can be done in constant time. Therefore, the second traversal also takes O(n) time.
Space complexity: O(1)
- We only need to update several parameters,
cur_penalty,min_penaltyandearliest_hour, which takes O(1) space.
Alternative
class Solution {
public int bestClosingTime(String customers) {
// Start with closing at hour 0 and assume the current penalty is 0.
int minPenalty = 0, curPenalty = 0;
int earliestHour = 0;
for (int i = 0; i < customers.length(); i++) {
char ch = customers.charAt(i);
// If status in hour i is 'Y', moving it to open hours decrement
// penalty by 1. Otherwise, moving 'N' to open hours increment
// penalty by 1.
if (ch == 'Y') {
curPenalty--;
} else {
curPenalty++;
}
// Update earliestHour if a smaller penatly is encountered.
if (curPenalty < minPenalty) {
earliestHour = i + 1;
minPenalty = curPenalty;
}
}
return earliestHour;
}
}385. Mini Parser
Given a string s represents the serialization of a nested list, implement a parser to deserialize it and return the deserialized NestedInteger.
Each element is either an integer or a list whose elements may also be integers or other lists.
Example 1:
Input: s = "324"
Output: 324
Explanation: You should return a NestedInteger object which contains a single integer 324.Example 2:
Input: s = "[123,[456,[789]]]"
Output: [123,[456,[789]]]
Explanation: Return a NestedInteger object containing a nested list with 2 elements:
1. An integer containing value 123.
2. A nested list containing two elements:
i. An integer containing value 456.
ii. A nested list with one element:
a. An integer containing value 789/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* public interface NestedInteger {
* // Constructor initializes an empty nested list.
* public NestedInteger();
*
* // Constructor initializes a single integer.
* public NestedInteger(int value);
*
* // @return true if this NestedInteger holds a single integer, rather than a nested list.
* public boolean isInteger();
*
* // @return the single integer that this NestedInteger holds, if it holds a single integer
* // Return null if this NestedInteger holds a nested list
* public Integer getInteger();
*
* // Set this NestedInteger to hold a single integer.
* public void setInteger(int value);
*
* // Set this NestedInteger to hold a nested list and adds a nested integer to it.
* public void add(NestedInteger ni);
*
* // @return the nested list that this NestedInteger holds, if it holds a nested list
* // Return empty list if this NestedInteger holds a single integer
* public List<NestedInteger> getList();
* }
*/
class Solution {
public NestedInteger deserialize(String s) {
if(s.charAt(0) != '[') return new NestedInteger(Integer.valueOf(s));
Stack<NestedInteger> stack = new Stack<>();
int start = 1;
for(int i=0; i<s.length(); i++){
char c = s.charAt(i);
if(c == '['){
stack.push(new NestedInteger()); // start of a new obj
start = i+1; // next position is the start of the new number
} else if (c == ','){
NestedInteger parent = stack.peek();
if(start<i){
parent.add(new NestedInteger(Integer.valueOf(s.substring(start, i))));
}
start = i+1;
} else if (c==']'){
NestedInteger top = stack.pop();
if(start<i){
top.add(new NestedInteger(Integer.valueOf(s.substring(start, i))));
}
start = i+1;
if(!stack.isEmpty()) stack.peek().add(top);
else return top;
}
}
return null;
}
}