Random Coding Questions on Leetcode
Mostly array and strings questions
Unrelated section on thread creation with java
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;
// create thread pool
final ExecutorService executor = Executors.newFixedThreadPool(5); // num of threads
// submit tasks to thread
IntStream.range(1, 1000)
. forEach(id -> executor.submit(() -> {
// do whatever you want...
}));
// wait for all threads to finish
executor.shudown();
executor.awaitTermination(Long.MAX_VALUE, TimeUnit.NANOSECONDS);
Leet code 55 Jump Game
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
Example 1:
Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Leet Code 45 Jump Game II
Given an array of non-negative integers nums, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps. Return the minimum number of jumps you can make to reach the last index.
You can assume that you can always reach the last index.
Example 1:
Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.Example 2:
Input: nums = [2,3,0,1,4]
Output: 2
1306. Jump Game III
Given an array of non-negative integers arr, you are initially positioned at start index of the array. When you are at index i, you can jump to i + arr[i] or i - arr[i], check if you can reach to any index with value 0.
Notice that you can not jump outside of the array at any time.
Example 1:
Input: arr = [4,2,3,0,3,1,2], start = 5
Output: true
Explanation:
All possible ways to reach at index 3 with value 0 are:
index 5 -> index 4 -> index 1 -> index 3
index 5 -> index 6 -> index 4 -> index 1 -> index 3Example 2:
Input: arr = [4,2,3,0,3,1,2], start = 0
Output: true
Explanation:
One possible way to reach at index 3 with value 0 is:
index 0 -> index 4 -> index 1 -> index 3Example 3:
Input: arr = [3,0,2,1,2], start = 2
Output: false
Explanation: There is no way to reach at index 1 with value 0.class Solution {
public boolean canReach(int[] arr, int start) {
Queue<Integer> queue = new LinkedList<>();
queue.add(start);
HashSet<Integer> visited = new HashSet<>();
while(!queue.isEmpty()){
int curr = queue.poll();
if(visited.contains(curr)) continue;
visited.add(curr);
if(curr<0 || curr>=arr.length) continue;
if(arr[curr] == 0) return true;
queue.add(curr+arr[curr]);
queue.add(curr-arr[curr]);
}
return false;
}
}23rd April 2023: I think i am getting good at this leetcode game.
1871. Jump Game VII
You are given a 0-indexed binary string s and two integers minJump and maxJump. In the beginning, you are standing at index 0, which is equal to '0'. You can move from index i to index j if the following conditions are fulfilled:
i + minJump <= j <= min(i + maxJump, s.length - 1), ands[j] == '0'.
Return true if you can reach index s.length - 1 in s, or false otherwise.
Example 1:
Input: s = "011010", minJump = 2, maxJump = 3
Output: true
Explanation:
In the first step, move from index 0 to index 3.
In the second step, move from index 3 to index 5.Example 2:
Input: s = "01101110", minJump = 2, maxJump = 3
Output: falseThis is kinda hard.
class Solution {
public boolean canReach(String s, int minJ, int maxJ) {
int n = s.length();
int pre = 0; // pre means the number of previous position that we can jump from.
boolean[] dp = new boolean[n];
dp[0] = true;
for (int i = 1; i < n; ++i) {
if (i >= minJ && dp[i - minJ])
pre++;
if (i > maxJ && dp[i - maxJ - 1])
pre--; // of the above pre...how many were invalid?
dp[i] = pre > 0 && s.charAt(i) == '0';
}
return dp[n - 1];
}
}O(N) complexity.
Leet code 16 3Sum Closest
- Refer to the solution given by leetcode for more thorough understanding
Given an array nums of n integers 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)Solution:
At first, i thought of sorting the array and then using binary search where i would modify the start, middle and end values and sum their values to get one nearest to the target. But this method doesn’t pass all the test cases as binary search does not try out every combinations. Out of A values, i will only check the first, last and A/2 values which is inaccurate.
The correct solution is somewhat similar to mine except that it doesnt use binary search.
In the sorted array, we process each value from left to right. For value v, we need to find a pair which sum, ideally, is equal to target - v. We will track the smallest absolute difference between this sum and the target.
https://www.youtube.com/watch?v=qBr2hq4daWE
const threeSumClosest = (nums, target) => {
//sort the array;
nums = nums.sort((a,b)=>a-b);
//to store closestSum
let closestSum = Infinity;
//iterate the array
for (let i = 0; i < nums.length; i ++) {
//tracker
let left = i + 1;
let right = nums.length -1;
//iterate till we have all the combinations
while (left < right) {
//sum of the triplets
let sum = nums[i] + nums[left] + nums[right];
// calc closestSum
if (Math.abs(sum - target) < Math.abs(closestSum - target)) closestSum = sum;
//update the tracker
if (sum > target) {
right --
} else {
left ++
}
}
}
return closestSum;
};O(N²) time complexity.
The outer for loop iterates over each element in the nums array, resulting in a linear time complexity of O(n). Inside this loop, the compute function is called, which contains a nested while loop.
The nested while loop iterates through the remaining elements in the nums array, resulting in a linear time complexity of O(n) as well. Although the loop has two pointers (low and high) moving towards each other, the overall complexity is still considered linear because the loop's iterations depend on the size of the input array.
n is the size of array.
Leet code premium member questions 3Sum Smaller
Given an array of n integers nums and a 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:
Input: nums = [-2,0,1,3], and target = 2
Output: 2
Explanation: Because there are two triplets which sums are less than 2:
[-2,0,1]
[-2,0,3]class Solution {
public int threeSumSmaller(int[] nums, int target) {
int rst = 0;
Arrays.sort(nums);
for (int i = 0; i < nums.length-2; i++) {
int j = i+1;
int k = nums.length-1;
while (j < k) {
int num = nums[j]+nums[k]+nums[i];
if (num < target) {
rst += k-j;
j++;
} else {
k--;
}
}
}
return rst;
}
}
Leetcode 15 3Sum
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]
]
Leetcode 34 Find First and Last Position of a number in a sorted array containing numbers.
Hint: This is like binary search but tweaked version. Covered in CS2040 extra lecture notes.
Take note of the while loop conditions etc…
Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.
Your algorithm’s runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
Example 1:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]Example 2:
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]I wrote this answer myself.
class Solution {
public int[] searchRange(int[] nums, int target) {
int leftMost=-1;
int rightMost=-1;
int left=0;
int right=nums.length-1;
while(left<=right){
int mid = (left+right)/2;
if(nums[mid]==target){
leftMost = mid;
while(leftMost-1>=0 && nums[leftMost-1]==nums[mid]){
leftMost--;
}
rightMost = mid;
while(rightMost+1<nums.length && nums[rightMost+1]==nums[mid]){
rightMost++;
}
break;
} else if(nums[mid]>target){
right=mid-1;
} else {
left=mid+1;
}
}
return new int[]{leftMost, rightMost};
}
}Revise Counting Sort
- Check out CS Dojo explaination
Main steps:
- Iterate through the entire array and add count to another array keeping track of those frequencies of values.
- From left to right, add num[i]+num[i-1] for each i. This is to count the number of numbers before this i value.
- Shift all values to the right by one. Since we index by 0.
- The new array now contains the starting index for each value. For eg, num[i] represents the index of the first occurrence of value i in the sorted array.
Leetcode 75 Sort Colors
Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Note: You are not suppose to use the library’s sort function for this problem.
Example:
Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]Solution:
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0’s, 1’s, and 2’s, then overwrite array with total number of 0’s, then 1’s and followed by 2's.
Counting sort is a sorting algorithm that works by counting the frequency of each element in the input array and using that information to place each element in its correct sorted position. It has a linear time complexity of O(n+k), where n is the size of the input array and k is the range of the input values.
- Find the maximum value in the input array and create a counting array with size equal to that value plus one. Initialize all elements of the counting array to zero.
- Iterate through the input array and increment the count of the element at its corresponding index in the counting array.
- Iterate through the counting array and update each element with the sum of its value and the value of the previous element. This step ensures that the count of each element includes the count of all previous elements in the array.
- Create an output array with size equal to the input array.
- Iterate through the input array in reverse order and place each element in its correct position in the output array based on its count in the counting array. Decrement the count of each element in the counting array after placing it in the output array.
- The output array now contains the sorted elements.
Leet Code 56 Merge Intervals
Given a collection of intervals, merge all overlapping intervals.
Example 1:
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].Example 2:
Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.Solution:
Note that in order for my following solution to work, the order in which we iterate has to be ascending. The first char of each int[] has to be increasing each time. Hence we need to define our own comparator for Array.sort().
After sorting, we will loop through each int[] and check the current[0] with previous[1] to decide whether to merge with previous intervals or append a new one.
Tweak to question: Say you are given int[][] intervals and int[] single, you need to return a boolean value if single overlaps with any interval in intervals.
Below are the 4 possible intervals overlap scenarios
-------
--
--
-------
------
------
------
------
Below is a situation where there is no overlap
---
---To check for any overlaps, we just iterate through the given intervals and need to look at the conditions. interval1 being the single interval and interv2 being the one we are iterating (Can be reversed).
if(interval1[0]≤interval2[1] && interval1[1]≥interval2[0])
57. Insert Interval
Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.
Example 1:
Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]Example 2:
Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].Example 3:
Input: intervals = [], newInterval = [5,7]
Output: [[5,7]]Example 4:
Input: intervals = [[1,5]], newInterval = [2,3]
Output: [[1,5]]Example 5:
Input: intervals = [[1,5]], newInterval = [2,7]
Output: [[1,7]]
Leet Code 435. Non-overlapping Intervals
Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.
Example 1:
Input: [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of intervals are non-overlapping.Example 2:
Input: [[1,2],[1,2],[1,2]]
Output: 2
Explanation: You need to remove two [1,2] to make the rest of intervals non-overlapping.Example 3:
Input: [[1,2],[2,3]]
Output: 0
Explanation: You don't need to remove any of the intervals since they're already non-overlapping.
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
if(intervals.length==0) return 0;
Arrays.sort(intervals, (a, b) -> a[0]-b[0]);
int maxEnd=intervals[0][1];
int count=0;
for(int i=1; i<intervals.length; i++){
if(intervals[i][0] < maxEnd){
maxEnd = Math.min(maxEnd, intervals[i][1]); // use min
// since we want to remove a minimum num of intervals
count++;
} else{
maxEnd=intervals[i][1];
}
}
return count;
}
}228. Summary Ranges
You are given a sorted unique integer array nums.
Return the smallest sorted list of ranges that cover all the numbers in the array exactly. That is, each element of nums is covered by exactly one of the ranges, and there is no integer x such that x is in one of the ranges but not in nums.
Each range [a,b] in the list should be output as:
"a->b"ifa != b"a"ifa == b
Example 1:
Input: nums = [0,1,2,4,5,7]
Output: ["0->2","4->5","7"]
Explanation: The ranges are:
[0,2] --> "0->2"
[4,5] --> "4->5"
[7,7] --> "7"Example 2:
Input: nums = [0,2,3,4,6,8,9]
Output: ["0","2->4","6","8->9"]
Explanation: The ranges are:
[0,0] --> "0"
[2,4] --> "2->4"
[6,6] --> "6"
[8,9] --> "8->9"Example 3:
Input: nums = []
Output: []Example 4:
Input: nums = [-1]
Output: ["-1"]Example 5:
Input: nums = [0]
Output: ["0"]class Solution {
public List<String> summaryRanges(int[] nums) {
List<String> result = new LinkedList<>();
List<int[]> resultList = new LinkedList<>();
for(int i=0; i<nums.length; i++){
if(resultList.size()==0){
resultList.add(new int[] {nums[i], nums[i]});
} else{
int[] prev = resultList.get(resultList.size()-1);
if(nums[i] - prev[1] == 1){
prev[1]=nums[i];
} else {
resultList.add(new int[] {nums[i], nums[i]});
}
}
}
for(int[] r: resultList){
if(r[0] != r[1]){
result.add(r[0]+"->"+r[1]);
} else {
result.add(String.valueOf(r[0]));
}
}
return result;
}
}Note that if the conditions are swapped, it doesn’t work. It fails this testcase: [-2147483648,-2147483647,2147483647]. Diff is -1 and -2 respectively and the code keeps entering the else.
if(nums[i] - prev[1] > 1){
resultList.add(new int[] {nums[i], nums[i]});
} else {
prev[1]=nums[i];
}1326. Minimum Number of Taps to Open to Water a Garden
There is a one-dimensional garden on the x-axis. The garden starts at the point 0 and ends at the point n. (i.e The length of the garden is n).
There are n + 1 taps located at points [0, 1, ..., n] in the garden.
Given an integer n and an integer array ranges of length n + 1 where ranges[i] (0-indexed) means the i-th tap can water the area [i - ranges[i], i + ranges[i]] if it was open.
Return the minimum number of taps that should be open to water the whole garden, If the garden cannot be watered return -1.
Example 1:
Input: n = 5, ranges = [3,4,1,1,0,0]
Output: 1
Explanation: The tap at point 0 can cover the interval [-3,3]
The tap at point 1 can cover the interval [-3,5]
The tap at point 2 can cover the interval [1,3]
The tap at point 3 can cover the interval [2,4]
The tap at point 4 can cover the interval [4,4]
The tap at point 5 can cover the interval [5,5]
Opening Only the second tap will water the whole garden [0,5]Example 2:
Input: n = 3, ranges = [0,0,0,0]
Output: -1
Explanation: Even if you activate all the four taps you cannot water the whole garden.Example 3:
Input: n = 7, ranges = [1,2,1,0,2,1,0,1]
Output: 3Example 4:
Input: n = 8, ranges = [4,0,0,0,0,0,0,0,4]
Output: 2Example 5:
Input: n = 8, ranges = [4,0,0,0,4,0,0,0,4]
Output: 1
Similar to the number range questions.
Convert the input into in[], similar to the the range question input..
Leet Code 79 Word Search
Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
Example:
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.
Permutations Sequence
The brute force solution would be to enumerate all permutations. Then, you return the kth sequence. Can we do better?
First, it’s important to understand why a sequence of n items can be ordered in n! ways.
When you want to find the number of orderings for n items, you have n possible slots to place the items in.
For the first slot, you have n choices.
For the second slot, you have (n - 1) choices.
You have (n - 2) choices for the third slot and so on.
The last slot will have 1 choice, which is the last remaining item.
You can find the total number of choices by multiplying the number of choices at each slot together.
The total number of choices = n * (n - 1) * (n -2) *…* 1 or n!.
If you want to find the number of orderings for (n-1) items, then it will be (n-1)!.
So, we have a sequence of numbers of [1,2,…, n] and we want to find the kth sequence.
How many sequences start with 1?
Well, if we pick 1 for the first slot, then there are (n-1) remaining numbers. That means that there are (n-1)! sequences that start with 1.
If k is less than (n-1)!, then we know that the kth sequence starts with 1.
If k is greater, then we can check the sequences that start with 2, the next (n-1)! sequences.
Once we figure out the first digit for the kth sequence, then we can apply the same logic for the second digit.
How many sequences start with “1” and then have a “2”?
It would be (n-2)! since we’ve picked the first two slots.
We can keep doing this recursively to find the kth sequence.
The way we code it is with a while loop.
We find the first digit by dividing k by n!.
The quotient tells us what the digit will be and the remainder gives us the value of k for the remaining digits.
We continuously repeat this process until we’ve filed up all the slots in our permutation of n digits and identified the kth permutation.
Infix, Prefix, Postfix Expressions
Prefix: The operators are for the two operands behind it. (right)
Postfix: The operators are for the two operands in front of it. (left)
<<Postfix -> Infix>>
Iterate left to right
If it is operand, push to stack
If it is operator, Pop from stack 2 items -> combine them into a string popsecond+operator+popfirst -> Add back to stack.
<<Postfix -> Prefix>>
Iterate left to right
If it is operand, push to stack
If it is operator, Pop from stack 2 items -> combine them into a string operator+popsecond+popfirst -> Add back to stack.
The only diff from above is how you combine the strings.
<<Prefix -> Postfix>>
Iterate right to left
If it is operand, push into stack
If it is operator, pop 2 items from stack -> combine them into a string firstPopped+secondPopped+operator -> push back into stack
<<Prefix -> Infix>>
Iterate Right to left
If it is operand, push into stack
If it is operator, pop 2 items from stack -> combine them into a string firstPopped+operator+secondPopped-> push back into stack
For infix, we need to take note of the operator precedences. It is harder….
<<Infix -> Postfix>>
Iterate left to right
If it is operand, we add to result String
If it is operator, We check if the stack contains an operator of higher precedence. If yes, we add those in the stack into the result. When done, we add current operator into the stack.
When we have finished, we pop from the stack and add to result string.
<<Infix -> Prefix>>
Reverse the given infix expression.
Change all the ( to ) and change ) to (.
The changed expression in infix form is to be converted into postfix form.
The evaluated postfix form is to be reversed to get the prefix form.
Prefix to Postfix
Prefix to Postfix
-> Read from right to left.
-> If it is an operand, we push into the stack.
-> If it is an operator, we pop 2 values out from the stack “CD-”. Put them together and push into the stack again.
Infix to Postfix
If the current char is an operand, we push into the result.
Otherwise, if it is an operator, we will check if the stack contains any operator of higher precedence. If yes, we add them to the result. Then, when done, we will add current operator to the stack and continue.
When we have finished evaluating the expression, we can then pop everything from the stack and add to the result.
(With Brackets)
The only change here is that we also add opening brackets to the stack. We also make a change to the WHILE Loop condition. When we encounter a closing bracket, we will then pop out everything from the stack until we see an opening bracket.
Infix to Prefix
TODO
118. Pascal’s Triangle
Given a non-negative integer numRows, generate the first numRows of Pascal’s triangle.
In Pascal’s triangle, each number is the sum of the two numbers directly above it.
Example:
Input: 5
Output:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]
223. Rectangle Area
Find the total area covered by two rectilinear rectangles in a 2D plane.
Each rectangle is defined by its bottom left corner and top right corner as shown in the figure.
Example:
Input: A = -3, B = 0, C = 3, D = 4, E = 0, F = -1, G = 9, H = 2
Output: 45
263. Ugly Number
Write a program to check whether a given number is an ugly number.
Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.
Example 1:
Input: 6
Output: true
Explanation: 6 = 2 × 3Example 2:
Input: 8
Output: true
Explanation: 8 = 2 × 2 × 2Example 3:
Input: 14
Output: false
Explanation: 14 is not ugly since it includes another prime factor 7.
264. Ugly Number II
Write a program to find the n-th ugly number.
Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.
Example:
Input: n = 10
Output: 12
Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.
313. Super Ugly Number
Write a program to find the nth super ugly number.
Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k.
Example:
Input: n = 12, primes = [2,7,13,19]
Output: 32
Explanation: [1,2,4,7,8,13,14,16,19,26,28,32] is the sequence of the first 12 super ugly numbers given primes = [2,7,13,19] of size 4.
I tried resolving it by adding a HashMap to track a number and whether it is prime so we don’t need to call isPrime method so much. But it didnt help.
This is the correct solution. It is a generalised form for Ugly Numbers II question.
299. Bulls and Cows
You are playing the Bulls and Cows game with your friend.
You write down a secret number and ask your friend to guess what the number is. When your friend makes a guess, you provide a hint with the following info:
- The number of “bulls”, which are digits in the guess that are in the correct position.
- The number of “cows”, which are digits in the guess that are in your secret number but are located in the wrong position. Specifically, the non-bull digits in the guess that could be rearranged such that they become bulls.
Given the secret number secret and your friend's guess guess, return the hint for your friend's guess.
The hint should be formatted as "xAyB", where x is the number of bulls and y is the number of cows. Note that both secret and guess may contain duplicate digits.
Example 1:
Input: secret = "1807", guess = "7810"
Output: "1A3B"
Explanation: Bulls are connected with a '|' and cows are underlined:
"1807"
|
"7810"Example 2:
Input: secret = "1123", guess = "0111"
Output: "1A1B"
Explanation: Bulls are connected with a '|' and cows are underlined:
"1123" "1123"
| or |
"0111" "0111"
Note that only one of the two unmatched 1s is counted as a cow since the non-bull digits can only be rearranged to allow one 1 to be a bull.Example 3:
Input: secret = "1", guess = "0"
Output: "0A0B"Example 4:
Input: secret = "1", guess = "1"
Output: "1A0B"This question is quite easy…
bulls will increment when there is a match of chars in secret and guess.
if no match, we will count the number of occurrence for each char in both secret and guess.
eventually we traverse through the 2 hashmaps to count number of cows.
1375. Bulb Switcher III (This qns seems to have disappeared from Leetcode —year 2023)
There is a room with n bulbs, numbered from 1 to n, arranged in a row from left to right. Initially, all the bulbs are turned off.
At moment k (for k from 0 to n - 1), we turn on the light[k] bulb. A bulb change color to blue only if it is on and all the previous bulbs (to the left) are turned on too.
Return the number of moments in which all turned on bulbs are blue.
Example 1:
Input: light = [2,1,3,5,4]
Output: 3
Explanation: All bulbs turned on, are blue at the moment 1, 2 and 4.Example 2:
Input: light = [3,2,4,1,5]
Output: 2
Explanation: All bulbs turned on, are blue at the moment 3, and 4 (index-0).Example 3:
Input: light = [4,1,2,3]
Output: 1
Explanation: All bulbs turned on, are blue at the moment 3 (index-0).
Bulb 4th changes to blue at the moment 3.Example 4:
Input: light = [2,1,4,3,6,5]
Output: 3Example 5:
Input: light = [1,2,3,4,5,6]
Output: 6
Discussion
public int numTimesAllBlue(int[] light) {
int allBlueCount = 0;
int maxIndexOn = 0;
for (int i = 0; i < light.length; i++) {
maxIndexOn = Math.max(maxIndexOn, light[i]);
if (i + 1 == maxIndexOn) {
allBlueCount++;
}
}
return allBlueCount;
}121. Best Time to Buy and Sell Stock
You are given an array prices where prices[i] is the price of a given stock on the ith day.
You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.
Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.
Example 1:
Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.Example 2:
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.class Solution {
public int maxProfit(int[] prices) {
// brute force: At each i, buy. Then iterate the values to the right to find max profit
// o(n^2) solution
// O(n) soln?
// min so far....
int min = prices[0];
int maxProfit = 0;
for(int i=1; i<prices.length; i++){
if(prices[i] > min){
maxProfit=Math.max(maxProfit, prices[i]-min);
}
if (prices[i]<min){
min = prices[i];
}
}
return maxProfit;
}
}122. Best Time to Buy and Sell Stock II
You are given an integer array prices where prices[i] is the price of a given stock on the ith day.
On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.
Find and return the maximum profit you can achieve.
Example 1:
Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.Example 2:
Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Total profit is 4.Example 3:
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.
class Solution {
public int maxProfit(int[] prices) {
int max = 0;
for(int p=1; p<prices.length; p++){
if(prices[p]>prices[p-1]){
max+=prices[p]-prices[p-1];
}
}
return max;
}
}2291. Maximum Profit From Trading Stocks (premium)
You are given two 0-indexed integer arrays of the same length present and future where present[i] is the current price of the ith stock and future[i] is the price of the ith stock a year in the future. You may buy each stock at most once. You are also given an integer budget representing the amount of money you currently have.
Return the maximum amount of profit you can make.
Example 1:
Input: present = [5,4,6,2,3], future = [8,5,4,3,5], budget = 10
Output: 6
Explanation: One possible way to maximize your profit is to:
Buy the 0th, 3rd, and 4th stocks for a total of 5 + 2 + 3 = 10.
Next year, sell all three stocks for a total of 8 + 3 + 5 = 16.
The profit you made is 16 - 10 = 6.
It can be shown that the maximum profit you can make is 6.Example 2:
Input: present = [2,2,5], future = [3,4,10], budget = 6
Output: 5
Explanation: The only possible way to maximize your profit is to:
Buy the 2nd stock, and make a profit of 10 - 5 = 5.
It can be shown that the maximum profit you can make is 5.Example 3:
Input: present = [3,3,12], future = [0,3,15], budget = 10
Output: 0
Explanation: One possible way to maximize your profit is to:
Buy the 1st stock, and make a profit of 3 - 3 = 0.
It can be shown that the maximum profit you can make is 0.Leet code solution (The following is from a solution submitted by another leetcode user)
For each new stock, we can either buy or not buy, so for each budget, we check if we can buy or not buy.
This means that the outer for loop is the stock with the inner loop being the budget.
We will only buy a stock when doing so makes a profit.
Let dp[i][j] be the maximum profit that can be made with budget j and 0 ~ ith stock.
Then, we have dp[i][j] = max(dp[i-1][j - present[i]] + future[i] - present[i], dp[i-1][j])
This dp only depends on the previous row, hence we have no need for 2D dp, let’s write it in 1D && since j - present[i] is only ever smaller than j, we can loop it backward to get rid of the need to create a tmp 1D array.
Time Complexity: O(budget * len of stock)
Space Complexity: O(budget)
class Solution {
public int maximumProfit(int[] present, int[] future, int budget) {
int[] dp = new int[budget+1]; // dp[i]: max profit if we consider up till the budget
for(int i=0; i<present.length; i++){
for(int j=budget; j>=0; j--){
if(future[i]-present[i] > 0 && j>=present[i]){ // can afford to buy ith stock and there's growth
int growth = future[i]-present[i];
dp[j] = Math.max(dp[j], dp[j - present[i]] + growth);
// dp[j - present[i]]: buying remainder stock...
}
}
}
return dp[budget];
}
}// wrong solution.. time limit exceeded
class Solution {
int max;
HashSet<HashSet<Integer>> visited;
public int maximumProfit(int[] present, int[] future, int budget) {
int[] diff = new int[present.length];
visited = new HashSet<>();
for(int i=0; i<present.length; i++){
diff[i]=future[i]-present[i];
}
max = 0;
helper(diff, present, budget, 0, new boolean[present.length]);
return max;
}
public void helper(int[] diff, int [] present, int budget, int profit, boolean[] taken){
HashSet<Integer> takenConverted = new HashSet<>();
for(int i=0; i<taken.length; i++){
if(taken[i]) takenConverted.add(i);
}
if (visited.contains(takenConverted)) return;
visited.add(takenConverted);
max = Math.max(profit, max);
for(int i=0; i<diff.length; i++){
if(taken[i]) continue;
if (budget-present[i] >= 0){
helper(diff, present, budget-present[i], profit+diff[i], setTaken(taken, i));
}
}
}
public boolean[] setTaken(boolean[] taken, int index){
boolean[] newTaken = new boolean[taken.length];
for(int i=0; i<taken.length; i++){
if(taken[i] || i==index){
newTaken[i]=true;
} else {
newTaken[i]=false;
}
}
return newTaken;
}
}714. Best Time to Buy and Sell Stock with Transaction Fee
You are given an array prices where prices[i] is the price of a given stock on the ith day, and an integer fee representing a transaction fee.
Find the maximum profit you can achieve. You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction.
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Example 1:
Input: prices = [1,3,2,8,4,9], fee = 2
Output: 8
Explanation: The maximum profit can be achieved by:
- Buying at prices[0] = 1
- Selling at prices[3] = 8
- Buying at prices[4] = 4
- Selling at prices[5] = 9
The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.Example 2:
Input: prices = [1,3,7,5,10,3], fee = 3
Output: 6
class Solution {
public int maxProfit(int[] prices, int fee) {
int buy = 0;
int sell = -prices[0]; // previously bought stock in order to reach current state of being able to sell
for(int i=1; i<prices.length; i++){
buy = Math.max(buy, sell+prices[i]-fee); // state of being ready to buy stock today
// buy: Previously was also ready to buy but didn't take any action.
// sell-prices[i]-fee: Previously sold stock with fee and received prices[i]-fee amount..
sell=Math.max(sell, buy-prices[i]);
// sell: Previously was ready to sell but didn't take any action
// buy-prices[i]. Previously bought a stock and spent prices[i]
}
return buy; // always want to end at a state where there is no outstanding
// stock left to sell.
}
}mind blown…
309. Best Time to Buy and Sell Stock with Cooldown
You are given an array prices where prices[i] is the price of a given stock on the ith day.
Find the maximum profit you can achieve. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times) with the following restrictions:
- After you sell your stock, you cannot buy stock on the next day (i.e., cooldown one day).
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Example 1:
Input: prices = [1,2,3,0,2]
Output: 3
Explanation: transactions = [buy, sell, cooldown, buy, sell]Example 2:
Input: prices = [1]
Output: 0
class Solution {
public int maxProfit(int[] prices) {
int sold = Integer.MIN_VALUE;
int held = Integer.MIN_VALUE;
int reset = 0;
for(int price: prices){
int preSold = sold;
sold = held+price;
held=Math.max(held, reset-price);
reset=Math.max(reset, preSold);
}
return Math.max(sold, reset);
}
}
123. Best Time to Buy and Sell Stock III
You are given an array prices where prices[i] is the price of a given stock on the ith day.
Find the maximum profit you can achieve. You may complete at most two transactions.
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Example 1:
Input: prices = [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.Example 2:
Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.Example 3:
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.// Time limit exceeded solution
class Solution {
public int maxProfit(int[] prices) {
// Pad both ends
int[] paddedPrices = new int[prices.length+2];
paddedPrices[0]=Integer.MAX_VALUE;
paddedPrices[paddedPrices.length-1]=Integer.MAX_VALUE;
int j=1;
int k=0;
while(j<paddedPrices.length-1){
paddedPrices[j]=prices[k];
k++;
j++;
}
// Separate prices into 2 halves
int max = 0;
for(int i=0; i<paddedPrices.length; i++){
int left = helper(paddedPrices, 0, i);
int right = helper(paddedPrices, i+1, paddedPrices.length-1);
max = Math.max(max, left+right);
}
return max;
}
public int helper(int[] prices, int start, int end){
if (start>prices.length-1 || end < 0) return 0;
int min = prices[start];
int maxProfit = 0;
for(int i=start+1; i<=end; i++){
if(prices[i] > min && prices[i] != Integer.MAX_VALUE){
maxProfit=Math.max(maxProfit, prices[i]-min);
}
if (prices[i]<min){
min = prices[i];
}
}
return maxProfit;
}
}
class Solution {
public int maxProfit(int[] prices) {
int length = prices.length;
if (length <= 1) return 0;
int leftMin = prices[0];
int[] leftProfits = new int[length];
for(int i=1; i<length; i++){
leftProfits[i] = Math.max(leftProfits[i-1], prices[i]-leftMin);
leftMin = Math.min(leftMin, prices[i]);
}
int rightMax = prices[length-1];
int[] rightProfits = new int[length];
for(int i=length-2; i>=0; i--){
rightProfits[i] = Math.max(rightProfits[i+1], rightMax-prices[i]);
rightMax = Math.max(rightMax, prices[i]);
}
int maxProfit = 0;
for(int i=0; i<length; i++){
if(i+1 < length){
maxProfit=Math.max(maxProfit, leftProfits[i]+ rightProfits[i+1]);
} else {
maxProfit=Math.max(maxProfit, leftProfits[i]);
}
}
return maxProfit;
}
}Idea: separate the arr into 2 halves…
188. Best Time to Buy and Sell Stock IV
You are given an integer array prices where prices[i] is the price of a given stock on the ith day, and an integer k.
Find the maximum profit you can achieve. You may complete at most k transactions: i.e. you may buy at most k times and sell at most k times.
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Example 1:
Input: k = 2, prices = [2,4,1]
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.Example 2:
Input: k = 2, prices = [3,2,6,5,0,3]
Output: 7
Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4. Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.Leetcode solution
The general idea is to store all consecutively increasing subsequence as the initial solution. Then delete or merge transactions until the number of transactions less than or equal to k.
public class Solution {
public int maxProfit(int k, int[] prices) {
int n = prices.length;
// solve special cases
if (n <= 0 || k <= 0) {
return 0;
}
// find all consecutively increasing subsequence
ArrayList<int[]> transactions = new ArrayList<>();
int start = 0;
int end = 0;
for (int i = 1; i < n; i++) {
if (prices[i] >= prices[i - 1]) {
end = i;
} else {
// restart
if (end > start) {
int[] t = { start, end };
transactions.add(t);
}
start = i;
}
}
if (end > start) {
int[] t = { start, end };
transactions.add(t);
}
while (transactions.size() > k) {
// check delete loss
int delete_index = 0;
int min_delete_loss = Integer.MAX_VALUE;
for (int i = 0; i < transactions.size(); i++) {
int[] t = transactions.get(i);
int profit_loss = prices[t[1]] - prices[t[0]];
if (profit_loss < min_delete_loss) {
min_delete_loss = profit_loss;
delete_index = i;
}
}
// check merge loss
int merge_index = 0;
int min_merge_loss = Integer.MAX_VALUE;
for (int i = 1; i < transactions.size(); i++) {
int[] t1 = transactions.get(i - 1);
int[] t2 = transactions.get(i);
int profit_loss = prices[t1[1]] - prices[t2[0]];
if (profit_loss < min_merge_loss) {
min_merge_loss = profit_loss;
merge_index = i;
}
}
// delete or merge
if (min_delete_loss <= min_merge_loss) {
transactions.remove(delete_index);
} else {
int[] t1 = transactions.get(merge_index - 1);
int[] t2 = transactions.get(merge_index);
t1[1] = t2[1];
transactions.remove(merge_index);
}
}
int res = 0;
for (int[] t : transactions) {
res += prices[t[1]] - prices[t[0]];
}
return res;
}
}
Alternative DP solution
class Solution {
public int maxProfit(int k, int[] prices) {
// no transaction, no profit
if (k == 0) return 0;
// dp[k][0] = min cost you need to spend at most k transactions
// dp[k][1] = max profit you can achieve at most k transactions
int [][] dp = new int[k + 1][2];
for (int i = 0; i <= k; i++) dp[i][0] = 1000;
for (int i = 0; i < prices.length; i++) {
for (int j = 1; j <= k; j++) {
// price - dp[i - 1][1] is how much you need to spend
// i.e use the profit you earned from previous transaction to buy the stock
// we want to minimize it
dp[j][0] = Math.min(dp[j][0], prices[i] - dp[j - 1][1]);
// price - dp[i][0] is how much you can achieve from previous min cost
// we want to maximize it
dp[j][1] = Math.max(dp[j][1], prices[i] - dp[j][0]);
}
}
// return max profit at most k transactions
return dp[k][1];
}
}In the inner loop of the solution provided, the following line updates the minimum cost for the current transaction j:
dp[j][0] = Math.min(dp[j][0], prices[i] - dp[j - 1][1]);Here, dp[j - 1][1] represents the maximum profit achieved in the previous transaction. Therefore, prices[i] - dp[j - 1][1] represents the cost of buying the stock in the current transaction, because we need to use the maximum profit from the previous transaction to purchase the stock at the current price.
Now, we want to minimize the cost of buying the stock, because that will maximize the profit we can make from selling the stock later. Therefore, we take the minimum of the current minimum cost dp[j][0] and the cost of buying the stock prices[i] - dp[j - 1][1].
The following line updates the maximum profit for the current transaction j:
dp[j][1] = Math.max(dp[j][1], prices[i] - dp[j][0]);Here, dp[j][0] represents the minimum cost achieved up to the current transaction, because we want to maximize the profit we can make from selling the stock later. Therefore, we subtract the minimum cost from the current price to get the maximum profit we can make from selling the stock at the current price.
Now, we want to maximize the profit, so we take the maximum of the current maximum profit dp[j][1] and the maximum profit we can make from selling the stock at the current price prices[i] - dp[j][0].
845. Longest Mountain in Array
You may recall that an array arr is a mountain array if and only if:
arr.length >= 3- There exists some index
i(0-indexed) with0 < i < arr.length - 1such that: arr[0] < arr[1] < ... < arr[i - 1] < arr[i]arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
Given an integer array arr, return the length of the longest subarray, which is a mountain. Return 0 if there is no mountain subarray.
Example 1:
Input: arr = [2,1,4,7,3,2,5]
Output: 5
Explanation: The largest mountain is [1,4,7,3,2] which has length 5.Example 2:
Input: arr = [2,2,2]
Output: 0
Explanation: There is no mountain.class Solution {
public int longestMountain(int[] A) {
int maxx = 0;
int i = 1;
while (i < A.length) {
while (i < A.length && A[i-1] == A[i])
++i;
int up = 0;
while (i < A.length && A[i-1] < A[i]) {
++up;
++i;
}
int down = 0;
while (i < A.length && A[i-1] > A[i]) {
++down;
++i;
}
if (up > 0 && down > 0)
maxx = Math.max(maxx, up+down+1);
}
return maxx;
}
}670. Maximum Swap
You are given an integer num. You can swap two digits at most once to get the maximum valued number.
Return the maximum valued number you can get.
Example 1:
Input: num = 2736
Output: 7236
Explanation: Swap the number 2 and the number 7.Example 2:
Input: num = 9973
Output: 9973
Explanation: No swap.class Solution {
public int maximumSwap(int num) {
char[] numCharArr = String.valueOf(num).toCharArray();
char[] maxRight = new char[numCharArr.length];
int[] maxRightIndex = new int[numCharArr.length];
Arrays.fill(maxRight, '0');
Arrays.fill(maxRightIndex, -1);
for(int i=numCharArr.length-2; i>=0; i--){
if(maxRight[i+1]>=numCharArr[i+1]){ // must be =. This is because, we want to make sure we swap with a number to the rightmost... Eg, test: 1993. We want to swap 1 with the 9 in index 2 instead of index 1.
maxRight[i]=maxRight[i+1];
maxRightIndex[i]=maxRightIndex[i+1];
} else {
maxRight[i]=numCharArr[i+1];
maxRightIndex[i]=i+1;
}
}
for(int i=0; i<numCharArr.length; i++){
if(numCharArr[i] < maxRight[i]){
if (maxRightIndex[i] == -1){
continue;
}
// swap
char temp = numCharArr[i];
numCharArr[i]=maxRight[i];
numCharArr[maxRightIndex[i]]=temp;
break;
}
}
return Integer.parseInt(new String(numCharArr));
}
}1616. Split Two Strings to Make Palindrome
You are given two strings a and b of the same length. Choose an index and split both strings at the same index, splitting a into two strings: aprefix and asuffix where a = aprefix + asuffix, and splitting b into two strings: bprefix and bsuffix where b = bprefix + bsuffix. Check if aprefix + bsuffix or bprefix + asuffix forms a palindrome.
When you split a string s into sprefix and ssuffix, either ssuffix or sprefix is allowed to be empty. For example, if s = "abc", then "" + "abc", "a" + "bc", "ab" + "c" , and "abc" + "" are valid splits.
Return true if it is possible to form a palindrome string, otherwise return false.
Notice that x + y denotes the concatenation of strings x and y.
Example 1:
Input: a = "x", b = "y"
Output: true
Explaination: If either a or b are palindromes the answer is true since you can split in the following way:
aprefix = "", asuffix = "x"
bprefix = "", bsuffix = "y"
Then, aprefix + bsuffix = "" + "y" = "y", which is a palindrome.Example 2:
Input: a = "xbdef", b = "xecab"
Output: falseExample 3:
Input: a = "ulacfd", b = "jizalu"
Output: true
Explaination: Split them at index 3:
aprefix = "ula", asuffix = "cfd"
bprefix = "jiz", bsuffix = "alu"
Then, aprefix + bsuffix = "ula" + "alu" = "ulaalu", which is a palindrome.// Incorrect attempt...because of indexing issues. The population of the 4 stringp[
// is wrong
class Solution {
public boolean checkPalindromeFormation(String a, String b) {
if(a.length() == 1 && b.length()==1) return true;
String[] leftA = new String[a.length()+1];
String[] rightA = new String[a.length()+1];
String[] leftB = new String[a.length()+1];
String[] rightB = new String[a.length()+1];
for(int i=0; i<=a.length(); i++){
leftA[i]=a.substring(0, i).isEmpty() ? "#" : a.substring(0, i);
rightA[i]=reverseString(a.substring(i));
leftB[i]=b.substring(0, i).isEmpty() ? "#" : b.substring(0, i);
rightB[i]=reverseString(b.substring(i));
}
printArr(leftA);
// printArr(leftB);
// printArr(rightA);
printArr(rightB);
for(int i=0; i<rightB.length; i++){
if( (leftA[i].equals(rightB[i]) && leftA[i] != "" )|| (leftB[i].equals(rightA[i]) && leftB[i] != "")) return true;
}
return false;
}
public void printArr(String[] ls){
for(int i=0; i<ls.length; i++){
System.out.print(ls[i]);
System.out.print("-");
}
System.out.println();
}
public String reverseString(String str) {
if(str.isEmpty()) return "#";
StringBuilder sb = new StringBuilder(str);
sb.reverse();
return sb.toString();
}
}// Leetcode soln
class Solution {
boolean isPalindrome(String s, int i, int j) {
while (i < j && s.charAt(i) == s.charAt(j)) {
++i;
--j;
}
return i >= j; // if it finishes while loop,
// means is palindrome as every char is same...
}
boolean check(String a, String b) {
// Greedily use all matching letters from suffix and prefix.
// Then check if the middle of either string is a palindrome. (why?)
// This logic can be easily proven by a contradiction.
// Another way to think about this: using more characters from
// the both strings "shrinks" the middle part, so it increases the chance
// that the middle part is a palindrome.
int i = 0, j = a.length() - 1;
while (i < j && a.charAt(i) == b.charAt(j)) {
++i;
--j;
} // move towards the middle
return isPalindrome(a, i, j) || isPalindrome(b, i, j); // check palindrome for middle section
}
public boolean checkPalindromeFormation(String a, String b) {
return check(a, b) || check(b, a);
}
}Why do we need to check if the middle of either string is a palindrome?
- otherwise the entire string is not a palindrome
Restore IP Addresses
A valid IP address consists of exactly four integers separated by single dots. Each integer is between 0 and 255 (inclusive) and cannot have leading zeros.
- For example,
"0.1.2.201"and"192.168.1.1"are valid IP addresses, but"0.011.255.245","192.168.1.312"and"192.168@1.1"are invalid IP addresses.
Given a string s containing only digits, return all possible valid IP addresses that can be formed by inserting dots into s. You are not allowed to reorder or remove any digits in s. You may return the valid IP addresses in any order.
Example 1:
Input: s = "25525511135"
Output: ["255.255.11.135","255.255.111.35"]Example 2:
Input: s = "0000"
Output: ["0.0.0.0"]Example 3:
Input: s = "101023"
Output: ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]// Working soln that i came up with...but the code is quite messy
class Solution {
List<String> result;
public List<String> restoreIpAddresses(String s) {
result = new LinkedList<>();
helper(s, 0, "");
return result;
}
public void helper(String s, int dots, String newString){
if(dots==4 || s.isEmpty()){
if(validate(newString, s) && !result.contains(newString)){
// Prevent duplicate
result.add(newString);
}
return;
}
// The max num of digits (between 2 dots) are 3.
for(int i=1; i<=3; i++){
String remaining = "";
String currString = "";
if(s.length()>=i){
currString = s.substring(0, i);
remaining = s.substring(i);
} else {
currString = s;
remaining = "";
}
if(!newString.isEmpty()){
helper(remaining, dots+1, newString+"."+ currString);
} else{
// The beginning
helper(remaining, dots+1, currString);
}
}
}
public boolean validate(String s, String original){
if(original.length()!=0) return false; // Havent't finish using all chars in string
if (s.isEmpty()) return false; // New string is empty
String[] split = s.split("\\.");
if(split.length !=4) return false; // Don't have 4 dots
for(String str: split){
if((str.startsWith("0") && str.length()>1) || Integer.parseInt(str)<0 || Integer.parseInt(str)>255){
return false;
}
}
return true;
}
}// LEETCODE SOLUTION..maybe this is even more complicated lol
class Solution {
private boolean valid(String s, int start, int length) {
return length == 1 ||
(s.charAt(start) != '0' &&
(length < 3 ||
s.substring(start, start + length).compareTo("255") <= 0));
}
private void helper(String s, int startIndex, List<Integer> dots, List<String> ans) {
final int remainingLength = s.length() - startIndex;
final int remainingNumberOfIntegers = 4 - dots.size();
if (remainingLength > remainingNumberOfIntegers * 3 ||
remainingLength < remainingNumberOfIntegers) {
return;
}
if (dots.size() == 3) {
if (valid(s, startIndex, remainingLength)) {
StringBuilder sb = new StringBuilder();
int last = 0;
for (Integer dot : dots) {
sb.append(s.substring(last, last + dot));
last += dot;
sb.append('.');
}
sb.append(s.substring(startIndex));
ans.add(sb.toString());
}
return;
}
for (int curPos = 1; curPos <= 3 && curPos <= remainingLength; ++curPos) {
// Append a dot at the current position.
dots.add(curPos);
// Try making all combinations with the remaining string.
if (valid(s, startIndex, curPos)) {
helper(s, startIndex + curPos, dots, ans);
}
// Backtrack, i.e. remove the dot to try placing it at the next position.
dots.remove(dots.size() - 1);
}
}
public List<String> restoreIpAddresses(String s) {
List<String> ans = new ArrayList<>();
helper(s, 0, new ArrayList<>(), ans);
return ans;
}
}11. Container With Most Water
You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).
Find two lines that together with the x-axis form a container, such that the container contains the most water.
Return the maximum amount of water a container can store.
Notice that you may not slant the container.
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.Example 2:
Input: height = [1,1]
Output: 1class Solution {
public int maxArea(int[] height) {
int max = 0;
int left = 0;
int right = height.length-1;
while(left < right){
int width = right - left;
max = Math.max(max, Math.min(height[left], height[right]) * width);
if(height[left]<=height[right]){
left++;
} else {
right--;
}
}
return max;
}
}The intuition behind this approach is that the area formed between the lines will always be limited by the height of the shorter line. Further, the farther the lines, the more will be the area obtained.
We take two pointers, one at the beginning and one at the end of the array constituting the length of the lines. Futher, we maintain a variable maxarea to store the maximum area obtained till now. At every step, we find out the area formed between them, update maxarea and move the pointer pointing to the shorter line towards the other end by one step.
Initially we consider the area constituting the exterior most lines. Now, to maximize the area, we need to consider the area between the lines of larger lengths. If we try to move the pointer at the longer line inwards, we won’t gain any increase in area, since it is limited by the shorter line. But moving the shorter line’s pointer could turn out to be beneficial, as per the same argument, despite the reduction in the width. This is done since a relatively longer line obtained by moving the shorter line’s pointer might overcome the reduction in area caused by the width reduction.
Complexity Analysis
- Time complexity: O(n). Single pass.
- Space complexity: O(1). Constant space is used.
54. Spiral Matrix
Given an m x n matrix, return all elements of the matrix in spiral order.
Example 1:
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]Example 2:
Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> result = new LinkedList<>();
int rows = matrix.length;
int cols = matrix[0].length;
// boundaries
int upperRow = 0;
int lowerRow = matrix.length-1;
int leftCol = 0;
int rightCol = matrix[0].length-1;
while(result.size()<rows*cols){
// left to right
for(int j=leftCol; j<=rightCol; j++){
result.add(matrix[upperRow][j]);
}
// up to down
for(int j=upperRow+1; j<=lowerRow; j++){
result.add(matrix[j][rightCol]);
}
// right to left
if(lowerRow != upperRow){
for(int j=rightCol-1; j>=leftCol; j--){
result.add(matrix[lowerRow][j]);
}
}
// down to up
if(leftCol!=rightCol){
// Note the -1
// Note the end condition doesn't have equality...
for(int j=lowerRow-1; j>upperRow; j--){
result.add(matrix[j][leftCol]);
}
}
upperRow++;
lowerRow--;
leftCol++;
rightCol--;
}
return result;
}
}
398. Random Pick Index
Given an integer array nums with possible duplicates, randomly output the index of a given target number. You can assume that the given target number must exist in the array.
Implement the Solution class:
Solution(int[] nums)Initializes the object with the arraynums.int pick(int target)Picks a random indexifromnumswherenums[i] == target. If there are multiple valid i's, then each index should have an equal probability of returning.
Example 1:
Input
["Solution", "pick", "pick", "pick"]
[[[1, 2, 3, 3, 3]], [3], [1], [3]]
Output
[null, 4, 0, 2]Explanation
Solution solution = new Solution([1, 2, 3, 3, 3]);
solution.pick(3); // It should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.
solution.pick(1); // It should return 0. Since in the array only nums[0] is equal to 1.
solution.pick(3); // It should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.
class Solution {
private int[] nums;
private Random rand;
public Solution(int[] nums) {
this.nums = nums;
this.rand = new Random();
}
public int pick(int target) {
int n = this.nums.length;
int count = 0;
int idx = 0;
for (int i = 0; i < n; ++i) {
// if nums[i] is equal to target, i is a potential candidate
// which needs to be chosen uniformly at random
if (this.nums[i] == target) {
// increment the count of total candidates
// available to be chosen uniformly at random
count++;
// we pick the current number with probability 1 / count (reservoir sampling)
if (rand.nextInt(count) == 0) {
// rand.nextInt generates a random number where the upper bound (exclusive) is count.
idx = i;
}
}
}
return idx;
}
}91. Decode Ways
A message containing letters from A-Z can be encoded into numbers using the following mapping:
'A' -> "1"
'B' -> "2"
...
'Z' -> "26"To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, "11106" can be mapped into:
"AAJF"with the grouping(1 1 10 6)"KJF"with the grouping(11 10 6)
Note that the grouping (1 11 06) is invalid because "06" cannot be mapped into 'F' since "6" is different from "06".
Given a string s containing only digits, return the number of ways to decode it.
The test cases are generated so that the answer fits in a 32-bit integer.
Example 1:
Input: s = "12"
Output: 2
Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).Example 2:
Input: s = "226"
Output: 3
Explanation: "226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).Example 3:
Input: s = "06"
Output: 0
Explanation: "06" cannot be mapped to "F" because of the leading zero ("6" is different from "06").class Solution {
Map<String, Integer> memo = new HashMap<>();
public int numDecodings(String s) {
return decodeHelper(s);
}
public int decodeHelper(String s){
if(memo.containsKey(s)){
return memo.get(s);
}
if(s.length()==0){
return 1;
}
int count = 0;
for(int i=1; i<=2; i++){
if(i>s.length()) continue;
String beginning = s.substring(0, i);
if(!beginning.startsWith("0") && Integer.parseInt(beginning) <= 26 && Integer.parseInt(beginning) >= 1){
count += decodeHelper(s.substring(i));
}
}
memo.put(s, count);
return count;
}
}490. The Maze
There is a ball in a maze with empty spaces (represented as 0) and walls (represented as 1). The ball can go through the empty spaces by rolling up, down, left or right, but it won't stop rolling until hitting a wall. When the ball stops, it could choose the next direction.
Given the m x n maze, the ball's start position and the destination, where start = [startrow, startcol] and destination = [destinationrow, destinationcol], return true if the ball can stop at the destination, otherwise return false.
You may assume that the borders of the maze are all walls (see examples).
Example 1:
Input: maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [4,4]
Output: true
Explanation: One possible way is : left -> down -> left -> down -> right -> down -> right.Example 2:
Input: maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [3,2]
Output: false
Explanation: There is no way for the ball to stop at the destination. Notice that you can pass through the destination but you cannot stop there.Example 3:
Input: maze = [[0,0,0,0,0],[1,1,0,0,1],[0,0,0,0,0],[0,1,0,0,1],[0,1,0,0,0]], start = [4,3], destination = [0,1]
Output: falseclass Solution {
public boolean hasPath(int[][] maze, int[] start, int[] destination) {
boolean[][] visited = new boolean[maze.length][maze[0].length];
int[][] dirs = {{0,1},{0,-1},{-1,0},{1,0}};
Queue<int[]> queue = new LinkedList<>();
queue.add(start);
visited[start[0]][start[1]]=true;
while(!queue.isEmpty()){
int[] s = queue.remove();
if(s[0] == destination[0] && s[1] == destination[1]) return true;
for(int[] dir: dirs){
int x = s[0]+dir[0];
int y = s[1]+dir[1];
while(x>=0 && y>=0 && x<maze.length && y<maze[0].length && maze[x][y] == 0){
x+=dir[0];
y+=dir[1];
}
// x-dir[0] and y-dir[0] is the last valid position that is not out of bound
if (!visited[x - dir[0]][y-dir[1]]){
queue.add(new int[]{x-dir[0], y-dir[1]});
visited[x-dir[0]][y-dir[1]]=true;
}
}
}
return false;
}
}
// More intuitive but less clean code
class Solution {
public boolean hasPath(int[][] maze, int[] start, int[] destination) {
boolean [][] visited = new boolean[maze.length][maze[0].length];
Queue<int[]> queue = new LinkedList<int[]>();
queue.add(start);
while(queue.size()>0){
int[] curr = queue.poll();
// check all four directions
int x = curr[0];
int y = curr[1];
if(x==destination[0] && y==destination[1]) return true;
visited[x][y] = true;
int left = y;
while(left>=0 && maze[x][left] != 1){
left--;
}
System.out.println(left);
if(left != y && visited[x][left+1] != true){
queue.add(new int[]{x, left+1});
}
int right = y;
while(right<maze[0].length && maze[x][right] != 1){
right++;
}
if(right != y && visited[x][right-1] != true){
queue.add(new int[]{x, right-1});
}
int up = x;
while(up>=0 && maze[up][y] != 1){
up--;
}
if(up != x && visited[up+1][y] != true){
queue.add(new int[]{up+1, y});
}
int down = x;
while(down<maze.length && maze[down][y] != 1){
down++;
}
if(down != x && visited[down-1][y] != true){
queue.add(new int[]{down-1, y});
}
}
return false;
}
}735. Asteroid Collision
We are given an array asteroids of integers representing asteroids in a row.
For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed.
Find out the state of the asteroids after all collisions. If two asteroids meet, the smaller one will explode. If both are the same size, both will explode. Two asteroids moving in the same direction will never meet.
Example 1:
Input: asteroids = [5,10,-5]
Output: [5,10]
Explanation: The 10 and -5 collide resulting in 10. The 5 and 10 never collide.Example 2:
Input: asteroids = [8,-8]
Output: []
Explanation: The 8 and -8 collide exploding each other.Example 3:
Input: asteroids = [10,2,-5]
Output: [10]
Explanation: The 2 and -5 collide resulting in -5. The 10 and -5 collide resulting in 10.// my solution.... i feel very happy and relieved that i managed to solve this on my own.
// i am not so stupid after all
class Solution {
public int[] asteroidCollision(int[] asteroids) {
Stack<Integer> stack = new Stack<>();
for(int a: asteroids){
if(stack.size() == 0 || noCollide(stack, a)){
stack.push(a);
} else {
Boolean addA = false;
while(stack.size() > 0){
int absVal = Math.abs(a);
if (noCollide(stack, a)){
stack.push(a);
addA = false;
break;
} else if (absVal < stack.peek()){
addA = false;
break;
} else if (absVal == stack.peek()){
stack.pop();
// both cancel out
addA = false;
break;
} else if (absVal > stack.peek()){
stack.pop();
addA = true;
}
}
if(addA){
stack.add(a);
}
}
}
int[] result = new int[stack.size()];
int i = stack.size()-1;
while(stack.size()>0){
result[i] = stack.pop();
i--;
}
return result;
}
public boolean noCollide(Stack<Integer> stack, int a){
return (stack.peek() > 0 && a > 0) || (stack.peek() < 0 && a < 0 || (stack.peek() < 0 && a > 0));
}
}945. Minimum Increment to Make Array Unique
You are given an integer array nums. In one move, you can pick an index i where 0 <= i < nums.length and increment nums[i] by 1.
Return the minimum number of moves to make every value in nums unique.
The test cases are generated so that the answer fits in a 32-bit integer.
Example 1:
Input: nums = [1,2,2]
Output: 1
Explanation: After 1 move, the array could be [1, 2, 3].Example 2:
Input: nums = [3,2,1,2,1,7]
Output: 6
Explanation: After 6 moves, the array could be [3, 4, 1, 2, 5, 7].
It can be shown with 5 or less moves that it is impossible for the array to have all unique values.class Solution {
public int minIncrementForUnique(int[] nums) {
Arrays.sort(nums);
int[] numsCopy = Arrays.copyOf(nums, nums.length);
int count=0;
for(int i=1; i<nums.length; i++){
if(nums[i]<=numsCopy[i-1]){
numsCopy[i] = numsCopy[i-1]+1;
count += numsCopy[i]-nums[i];
} else{
numsCopy[i] = nums[i];
}
}
return count;
}
}2115. Find All Possible Recipes from Given Supplies
You have information about n different recipes. You are given a string array recipes and a 2D string array ingredients. The ith recipe has the name recipes[i], and you can create it if you have all the needed ingredients from ingredients[i]. Ingredients to a recipe may need to be created from other recipes, i.e., ingredients[i] may contain a string that is in recipes.
You are also given a string array supplies containing all the ingredients that you initially have, and you have an infinite supply of all of them.
Return a list of all the recipes that you can create. You may return the answer in any order.
Note that two recipes may contain each other in their ingredients.
Example 1:
Input: recipes = ["bread"], ingredients = [["yeast","flour"]], supplies = ["yeast","flour","corn"]
Output: ["bread"]
Explanation:
We can create "bread" since we have the ingredients "yeast" and "flour".Example 2:
Input: recipes = ["bread","sandwich"], ingredients = [["yeast","flour"],["bread","meat"]], supplies = ["yeast","flour","meat"]
Output: ["bread","sandwich"]
Explanation:
We can create "bread" since we have the ingredients "yeast" and "flour".
We can create "sandwich" since we have the ingredient "meat" and can create the ingredient "bread".Example 3:
Input: recipes = ["bread","sandwich","burger"], ingredients = [["yeast","flour"],["bread","meat"],["sandwich","meat","bread"]], supplies = ["yeast","flour","meat"]
Output: ["bread","sandwich","burger"]
Explanation:
We can create "bread" since we have the ingredients "yeast" and "flour".
We can create "sandwich" since we have the ingredient "meat" and can create the ingredient "bread".
We can create "burger" since we have the ingredient "meat" and can create the ingredients "bread" and "sandwich".class Solution {
public List<String> findAllRecipes(String[] recipes, List<List<String>> ingredients, String[] supplies) {
Set<String> seen = new HashSet<>();
for (String sup : supplies) {
seen.add(sup);
}
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < recipes.length; ++i) {
q.offer(i);
}
List<String> ans = new ArrayList<>();
int prevSize = seen.size() - 1;
while (seen.size() > prevSize) { // terminating condition is if we no longer see new supplies
prevSize = seen.size();
Queue<Integer> temp = new LinkedList<>();
// For every recipe in the queue, we check if it can be made by the supplies we have
for (int sz = q.size(); sz > 0; --sz) {
int i = q.poll();
boolean canMake = true;
for (String ing : ingredients.get(i)) {
if (!seen.contains(ing)) {
canMake = false;
break;
}
}
if (canMake) {
seen.add(recipes[i]);
ans.add(recipes[i]);
} else {
temp.offer(i); // add back recipe to the queue as it currently cannot be made
}
}
q.addAll(temp);
}
return ans;
}
}
/*
Can we use a data structure to quickly query whether we have a certain ingredient?
*Once we verify that we can make a recipe, we can add it to our ingredient data structure. We can then check if we can make more recipes as a result of this.
*/279. Perfect Squares
Given an integer n, return the least number of perfect square numbers that sum to n.
A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.
Example 1:
Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.Example 2:
Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.
class Solution {
public int numSquares(int n) {
ArrayList<Integer> square_nums = new ArrayList<Integer>();
for (int i = 1; i * i <= n; ++i) {
square_nums.add(i * i);
}
Set<Integer> queue = new HashSet<Integer>();
queue.add(n);
int level = 0;
while (queue.size() > 0) {
level += 1;
Set<Integer> next_queue = new HashSet<Integer>();
for (Integer remainder : queue) {
for (Integer square : square_nums) {
if (remainder.equals(square)) {
return level;
} else if (remainder < square) {
break;
} else {
next_queue.add(remainder - square);
}
}
}
queue = next_queue;
}
return level;
}
}
Time complexity: O(n^(n+1)) because in the worst case we can search n + 1 level in depth (worst case the perfect squares are made up all by 1s) from 0 and the tree can thus contains up to n^(n+1) nodes (n^0 + n^1 + n^2 + ... + n^(n-1) + n^n).
- Each level of the search tree corresponds to a possible solution, where the solution represents a combination of perfect squares that add up to the original number
- Since we can use perfect squares up to the value of n, the maximum number of nodes at each level would be n as we can form a sum of n using only 1s.
- For example, let’s consider n = 12. At level 0, we have only one node representing the number 12. At level 1, we can subtract any of the perfect squares up to 12 from 12 to obtain the values {11, 8, 3, 0}. Therefore, we have 4 nodes at level 1. At level 2, we can subtract any of the perfect squares up to 11, 8, 3, or 0, to obtain the possible values {10, 7, 2, -1, 5, 0, 3, -8}. We can see that the maximum number of nodes at each level is limited by n.
- In general, at each level, we can subtract any of the perfect squares up to n, which means that the number of nodes at each level is at most n.
Space complexity: O(n^n) because of the queue used to store each level we are iterating through.
1257. Smallest Common Region
You are given some lists of regions where the first region of each list includes all other regions in that list.
Naturally, if a region x contains another region y then x is bigger than y. Also, by definition, a region x contains itself.
Given two regions: region1 and region2, return the smallest region that contains both of them.
If you are given regions r1, r2, and r3 such that r1 includes r3, it is guaranteed there is no r2 such that r2 includes r3.
It is guaranteed the smallest region exists.
Example 1:
Input:
regions = [["Earth","North America","South America"],
["North America","United States","Canada"],
["United States","New York","Boston"],
["Canada","Ontario","Quebec"],
["South America","Brazil"]],
region1 = "Quebec",
region2 = "New York"
Output: "North America"Example 2:
Input: regions = [["Earth", "North America", "South America"],["North America", "United States", "Canada"],["United States", "New York", "Boston"],["Canada", "Ontario", "Quebec"],["South America", "Brazil"]], region1 = "Canada", region2 = "South America"
Output: "Earth"This question is quite similar to the question of lowest common ancestors…The idea is to build a HashMap where the key represent a place and the value represents the parent region.
Based on this Hashmap, for each region, use DFS to find out all it’s parents. Store them in a List. The first position in the list is the parent, second position is grand parent etc etc.
Then compare the two lists. Once we see a place that is found in both lists, we know that is the smallest region.
class Solution {
public String findSmallestRegion(List<List<String>> regions, String region1, String region2) {
HashMap<String, String> map = new HashMap<>();
for(List<String> reg : regions){
String first = reg.get(0);
for(int i=1; i<reg.size(); i++){
map.put(reg.get(i), first);
}
}
List<String> parent1 = findParents(region1, map);
List<String> parent2 = findParents(region2, map);
for(String p: parent1){
if(parent2.contains(p)){
return p;
}
}
return "";
}
public List<String> findParents(String region, HashMap<String, String> map){
List<String> result = new LinkedList<>();
result.add(region);
while(map.containsKey(region)){
String parent = map.get(region);
result.add(parent);
region = parent;
}
return result;
}
}287. Find the Duplicate Number
Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.
There is only one repeated number in nums, return this repeated number.
You must solve the problem without modifying the array nums and uses only constant extra space.
Example 1:
Input: nums = [1,3,4,2,2]
Output: 2Example 2:
Input: nums = [3,1,3,4,2]
Output: 3
class Solution {
public int findDuplicate(int[] nums) {
// Find the intersection point of the two runners.
int tortoise = nums[0];
int hare = nums[0];
do {
tortoise = nums[tortoise];
hare = nums[nums[hare]];
} while (tortoise != hare);
// Find the "entrance" to the cycle.
tortoise = nums[0];
while (tortoise != hare) {
tortoise = nums[tortoise];
hare = nums[hare];
}
return hare;
}
}i don’t really understand this…just pray it doesn’t come out during interviews.
13. Roman to Integer
Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.
Symbol Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000For example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.
Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:
Ican be placed beforeV(5) andX(10) to make 4 and 9.Xcan be placed beforeL(50) andC(100) to make 40 and 90.Ccan be placed beforeD(500) andM(1000) to make 400 and 900.
Given a roman numeral, convert it to an integer.
Example 1:
Input: s = "III"
Output: 3
Explanation: III = 3.Example 2:
Input: s = "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.Example 3:
Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.class Solution {
public int romanToInt(String s) {
HashMap<String, Integer> map = new HashMap<>();
map.put("I", 1);
map.put("V", 5);
map.put("X", 10);
map.put("L", 50);
map.put("C", 100);
map.put("D", 500);
map.put("M", 1000);
map.put("IV", 4);
map.put("IX", 9);
map.put("XL", 40);
map.put("XC", 90);
map.put("CD", 400);
map.put("CM", 900);
int start=0;
int result=0;
while(start<s.length()){
// Try to find match for 2 chars
if(start+2<=s.length()){ // make sure not out of bound
String firstTwoChar = s.substring(start, start+2);
if(map.containsKey(firstTwoChar)){
result += map.get(firstTwoChar);
start+=2;
continue;
}
}
// Try to find match for 1 char
String firstChar = s.substring(start, start+1);
result += map.get(firstChar);
start++;
}
return result;
}
}12. Integer to Roman
Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.
Symbol Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000For example, 2 is written as II in Roman numeral, just two one's added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.
Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:
Ican be placed beforeV(5) andX(10) to make 4 and 9.Xcan be placed beforeL(50) andC(100) to make 40 and 90.Ccan be placed beforeD(500) andM(1000) to make 400 and 900.
Given an integer, convert it to a roman numeral.
Example 1:
Input: num = 3
Output: "III"
Explanation: 3 is represented as 3 ones.Example 2:
Input: num = 58
Output: "LVIII"
Explanation: L = 50, V = 5, III = 3.Example 3:
Input: num = 1994
Output: "MCMXCIV"
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.class Solution {
public String intToRoman(int num) {
HashMap<String, Integer> map = new HashMap<>();
List<Info> sortedList = new LinkedList<>();
sortedList.add(new Info("I", 1));
sortedList.add(new Info("IV", 4));
sortedList.add(new Info("V", 5));
sortedList.add(new Info("IX", 9));
sortedList.add(new Info("X", 10));
sortedList.add(new Info("XL", 40));
sortedList.add(new Info("L", 50));
sortedList.add(new Info("XC", 90));
sortedList.add(new Info("C", 100));
sortedList.add(new Info("CD", 400));
sortedList.add(new Info("D", 500));
sortedList.add(new Info("CM", 900));
sortedList.add(new Info("M", 1000));
String result = "";
for(int i=sortedList.size()-1; i>=0; i--){
Info curr = sortedList.get(i);
while(num>=curr.value){
result+=curr.roman;
num-=curr.value;
}
}
return result;
}
public class Info{
String roman;
int value;
public Info(String roman, int value){
this.roman=roman;
this.value=value;
}
}
}Yay! Solved this in my first attempt.
Extra
The following is not exactly a Leetcode question..just an assignment i was given when interviewing with a company.
/*
Please write a function that accepts a single string as input, and that returns a list of English words that can be created using some combination of the letters in the input string.
Example input: "oogd"
Example output: ["good", "god", "dog", "goo", "do", "go"]
You can assume you'll be given an array of strings that enumerates all valid English words. To determine whether a word is a valid word, you can simply check for its presence in the array (e.g., `WORDS.includes(word)`)
*/
import java.util.*;
class Main {
private static HashSet<String> DICTIONARY = new HashSet<String>(Arrays.asList("good", "god", "dog", "goo", "do", "go", "a"));
public static void main(String[] args) {
System.out.println(wordsGenerator("oogd"));
System.out.println(wordsGenerator("aaaaaaaaa")); // Test with repeated chars
System.out.println(wordsGenerator("a")); // Test with single char
System.out.println(wordsGenerator("xyz")); // Test with invalid
System.out.println(wordsGenerator("")); // Test with empty
}
private static Set<String> wordsGenerator(String input){
HashSet<String> result = new HashSet<>();
Set<String> perms = generatePermutations(input);
for(String word: perms){
if(DICTIONARY.contains(word)){
result.add(word);
}
}
return result;
}
private static Set<String> generatePermutations(String input){
if(input.length()<=1){
return new HashSet<>(Collections.singletonList(input));
}
Set<String> allPerms = new HashSet<>();
String firstChar = input.substring(0, 1);
// only firstChar
allPerms.add(firstChar);
Set<String> remainderStringsSet = generatePermutations(input.substring(1));
for(String remainder: remainderStringsSet){
// without firstChar
allPerms.add(remainder);
// with firstChar
for(int i=0; i<=remainder.length(); i++){
String newString = remainder.substring(0, i)+firstChar+remainder.substring(i);
allPerms.add(newString);
}
}
return allPerms;
}
}
/*
Some points:
- memoisation may not be needed..this is because we are using bottom up approach and set.
- Use a StringBuilder to construct the new string when generating permutations, rather than concatenating substrings. This can improve the efficiency of the string concatenation operation.
The time complexity of the generatePermutations function is O(n!) where n is the length of the input string. This is because there are n! possible permutations of the input string.
Note that the actual number of permutations generated in the generatePermutations function is smaller than n!, because it avoids generating duplicates by storing the permutations in a set.
In terms of space complexity, the generatePermutations function has a space complexity of O(n!), because it needs to store all possible permutations of the input string in a set. The wordsGenerator function has a space complexity of O(m), where m is the number of valid English words that can be generated from the input string, because it stores the valid words in a set.
*/1094. Car Pooling
There is a car with capacity empty seats. The vehicle only drives east (i.e., it cannot turn around and drive west).
You are given the integer capacity and an array trips where trips[i] = [numPassengersi, fromi, toi] indicates that the ith trip has numPassengersi passengers and the locations to pick them up and drop them off are fromi and toi respectively. The locations are given as the number of kilometers due east from the car's initial location.
Return true if it is possible to pick up and drop off all passengers for all the given trips, or false otherwise.
Example 1:
Input: trips = [[2,1,5],[3,3,7]], capacity = 4
Output: falseExample 2:
Input: trips = [[2,1,5],[3,3,7]], capacity = 5
Output: true// My solution
class Solution {
public boolean carPooling(int[][] trips, int capacity) {
// sort trips
Arrays.sort(trips, (t1, t2) -> t1[1] - t2[1]);
int curr = 0;
for(int t=0; t<trips.length; t++){
int pass = trips[t][0];
int from = trips[t][1];
int to = trips[t][2];
// check if can subtract passengers from previous trips
for(int s = 0; s<t; s++){
int[] prev = trips[s];
if(prev[2] <= from){
curr -= prev[0];
prev[0] = 0; // set value of passengers to 0 to mark them as alighted
}
}
curr += pass;
if(curr>capacity) return false;
}
return true;
}
}
// O(N^2) solution From Leetcode’s editorial solution
A simple idea is to go through from the start to end, and check if the actual capacity exceeds capacity.
To know the actual capacity, we just need the number of passengers changed at each timestamp.
We can save the number of passengers changed at each time, sort it by timestamp, and finally iterate it to check the actual capacity.
Algorithm
We will initialize a list to store the number of passengers changed and the corresponding timestamp and then sort it.
Note that in Java, we do not have a nice API to do this. However, we can use a TreeMap, which can help us to sort during insertion. You can use a PriorityQueue instead.
Finally, we just need to iterate from the start timestamp to the end timestamp and check if the actual capacity meets the condition.
class Solution {
public boolean carPooling(int[][] trips, int capacity) {
Map<Integer, Integer> timestamp = new TreeMap<>();
for (int[] trip : trips) {
int startPassenger = timestamp.getOrDefault(trip[1], 0) + trip[0];
timestamp.put(trip[1], startPassenger);
int endPassenger = timestamp.getOrDefault(trip[2], 0) - trip[0];
timestamp.put(trip[2], endPassenger);
}
int usedCapacity = 0;
for (int passengerChange : timestamp.values()) {
usedCapacity += passengerChange;
if (usedCapacity > capacity) {
return false;
}
}
return true;
}
}Complexity Analysis
Assume N is the length of trips.
- Time complexity: O(Nlog(N)) since we need to iterate over
tripsand sort ourtimestamp. Iterating costs O(N), and sorting costs O(Nlog(N)), and adding together we have O(N)+O(Nlog(N))=O(Nlog(N)). - Space complexity: O(N) since in the worst case we need O(N) to store
timestamp.
Can consider: https://leetcode.com/problems/corporate-flight-bookings/
991. Broken Calculator
There is a broken calculator that has the integer startValue on its display initially. In one operation, you can:
- multiply the number on display by
2, or - subtract
1from the number on display.
Given two integers startValue and target, return the minimum number of operations needed to display target on the calculator.
Example 1:
Input: startValue = 2, target = 3
Output: 2
Explanation: Use double operation and then decrement operation {2 -> 4 -> 3}.Example 2:
Input: startValue = 5, target = 8
Output: 2
Explanation: Use decrement and then double {5 -> 4 -> 8}.Example 3:
Input: startValue = 3, target = 10
Output: 3
Explanation: Use double, decrement and double {3 -> 6 -> 5 -> 10}.Approach 1: Work Backwards
Intuition
Instead of multiplying by 2 or subtracting 1 from startValue, we could divide by 2 (when target is even) or add 1 to target.
The motivation for this is that it turns out we always greedily divide by 2:
- If say
targetis even, then if we perform 2 additions and one division, we could instead perform one division and one addition for less operations [(target + 2) / 2vstarget / 2 + 1]. - If say
targetis odd, then if we perform 3 additions and one division, we could instead perform 1 addition, 1 division, and 1 addition for less operations [(target + 3) / 2vs(target + 1) / 2 + 1].
Algorithm
While target is larger than startValue, add 1 if it is odd, else divide by 2. After, we need to do startValue - target additions to reach startValue.
class Solution {
public int brokenCalc(int startValue, int target) {
int ans = 0;
while(target > startValue){
ans++;
if(target % 2 == 0){
target /= 2;
} else {
target ++;
}
}
return ans + startValue - target;
}
}- Time Complexity: O(logtarget).
- Space Complexity: O(1)
Alternative
if startValue >= target, then we have to subtract startValue by 1
Otherwise,
if it is even, then the only way is to divide target by 2
If it is odd, then there's no way other than to add 1 to target to change it to even
Java
class Solution {
public int brokenCalc(int startValue, int target) {
if(startValue >= target) return startValue - target; # Number of -1 ops
if(target % 2 == 0){
return 1 + brokenCalc(startValue, target / 2);
}
return 1 + brokenCalc(startValue, target + 1);
}
}8. String to Integer (atoi)
Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer (similar to C/C++'s atoi function).
The algorithm for myAtoi(string s) is as follows:
- Read in and ignore any leading whitespace.
- Check if the next character (if not already at the end of the string) is
'-'or'+'. Read this character in if it is either. This determines if the final result is negative or positive respectively. Assume the result is positive if neither is present. - Read in next the characters until the next non-digit character or the end of the input is reached. The rest of the string is ignored.
- Convert these digits into an integer (i.e.
"123" -> 123,"0032" -> 32). If no digits were read, then the integer is0. Change the sign as necessary (from step 2). - If the integer is out of the 32-bit signed integer range
[-231, 231 - 1], then clamp the integer so that it remains in the range. Specifically, integers less than-231should be clamped to-231, and integers greater than231 - 1should be clamped to231 - 1. - Return the integer as the final result.
Note:
- Only the space character
' 'is considered a whitespace character. - Do not ignore any characters other than the leading whitespace or the rest of the string after the digits.
Example 1:
Input: s = "42"
Output: 42
Explanation: The underlined characters are what is read in, the caret is the current reader position.
Step 1: "42" (no characters read because there is no leading whitespace)
^
Step 2: "42" (no characters read because there is neither a '-' nor '+')
^
Step 3: "42" ("42" is read in)
^
The parsed integer is 42.
Since 42 is in the range [-231, 231 - 1], the final result is 42.Example 2:
Input: s = " -42"
Output: -42
Explanation:
Step 1: " -42" (leading whitespace is read and ignored)
^
Step 2: " -42" ('-' is read, so the result should be negative)
^
Step 3: " -42" ("42" is read in)
^
The parsed integer is -42.
Since -42 is in the range [-231, 231 - 1], the final result is -42.Example 3:
Input: s = "4193 with words"
Output: 4193
Explanation:
Step 1: "4193 with words" (no characters read because there is no leading whitespace)
^
Step 2: "4193 with words" (no characters read because there is neither a '-' nor '+')
^
Step 3: "4193 with words" ("4193" is read in; reading stops because the next character is a non-digit)
^
The parsed integer is 4193.
Since 4193 is in the range [-231, 231 - 1], the final result is 4193.class Solution {
public int myAtoi(String input) {
int sign = 1;
int result = 0;
int index = 0;
int n = input.length();
// Discard all spaces from the beginning of the input string.
while (index < n && input.charAt(index) == ' ') {
index++;
}
// sign = +1, if it's positive number, otherwise sign = -1.
if (index < n && input.charAt(index) == '+') {
sign = 1;
index++;
} else if (index < n && input.charAt(index) == '-') {
sign = -1;
index++;
}
// Traverse next digits of input and stop if it is not a digit
while (index < n && Character.isDigit(input.charAt(index))) {
int digit = input.charAt(index) - '0';
// Check overflow and underflow conditions.
if ((result > Integer.MAX_VALUE / 10) ||
(result == Integer.MAX_VALUE / 10 && digit > Integer.MAX_VALUE % 10)) {
// If integer overflowed return 2^31-1, otherwise if underflowed return -2^31.
return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
}
// Append current digit to the result.
result = 10 * result + digit;
index++;
}
// We have formed a valid number without any overflow/underflow.
// Return it after multiplying it with its sign.
return sign * result;
}
}10. Regular Expression Matching
Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where:
'.'Matches any single character.'*'Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
Example 1:
Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".Example 2:
Input: s = "aa", p = "a*"
Output: true
Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".Example 3:
Input: s = "ab", p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".class Solution {
private String text;
private String pattern;
public boolean isMatch(String text, String pattern) {
this.text = text;
this.pattern = pattern;
return dfs(0, 0);
}
public boolean dfs(int i, int j){
if (i>=text.length() && j>=pattern.length()){
return true;
}
if (j>=pattern.length()) return false;
boolean match = i < text.length() && (text.charAt(i) == pattern.charAt(j) || pattern.charAt(j) == '.');
if( (j+1) < pattern.length() && pattern.charAt(j+1) == '*'){
return dfs(i, j+2) // don't use star
|| (match && dfs(i+1, j)); // use star
}
if(match){
return dfs(i+1, j+1); // curr char matches
}
return false;
}
}class Solution {
private String text;
private String pattern;
HashMap<Pair<Integer, Integer>, Boolean> map;
public boolean isMatch(String text, String pattern) {
this.text = text;
this.pattern = pattern;
map = new HashMap<>();
return dfs(0, 0);
}
public boolean dfs(int i, int j){
Pair<Integer, Integer> curr = new Pair(i, j);
if (map.containsKey(curr)) return map.get(curr);
if (i>=text.length() && j>=pattern.length()){
return true;
}
if (j>=pattern.length()) return false;
boolean match = i < text.length() && (text.charAt(i) == pattern.charAt(j) || pattern.charAt(j) == '.');
if( (j+1) < pattern.length() && pattern.charAt(j+1) == '*'){
boolean val = dfs(i, j+2) // don't use star
|| (match && dfs(i+1, j)); // use star
map.put(curr, val);
return val;
}
if(match){
boolean val2 = dfs(i+1, j+1); // curr char matches
map.put(curr, val2);
return val2;
}
map.put(curr, false);
return false;
}
}
// Add some memoisation44. Wildcard Matching
Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*' where:
'?'Matches any single character.'*'Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).
Example 1:
Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".Example 2:
Input: s = "aa", p = "*"
Output: true
Explanation: '*' matches any sequence.Example 3:
Input: s = "cb", p = "?a"
Output: false
Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.class Solution {
private String text;
private String pattern;
HashMap<Pair<Integer, Integer>, Boolean> map;
public boolean isMatch(String text, String pattern) {
this.text = text;
this.pattern = pattern;
// trimBothEnds();
map = new HashMap<>();
return dfs(0, 0);
}
// Remove common chars on both ends that appear in text and pattern
// Eg, abcdefg and ab*fg becomes cde and *
// This helps to save some time...but is optional and not needed.
/* public void trimBothEnds(){
int i=0;
while(i<text.length() && i<pattern.length()){
if(text.charAt(i)==pattern.charAt(i)){
i++;
} else {
break;
}
}
text = text.substring(i);
pattern = pattern.substring(i);
int j=text.length()-1;
int j2 = pattern.length()-1;
while(j>=0 && j2 >=0){
if(text.charAt(j) == pattern.charAt(j2)){
j2--;
j--;
} else {
break;
}
}
text = j<0 ? "" : text.substring(0, j+1);
pattern = j2<0 ? "" : pattern.substring(0, j2+1);
}
*/
public boolean dfs(int i, int j){
Pair<Integer, Integer> curr = new Pair(i, j);
if (map.containsKey(curr)) return map.get(curr);
if (i>=text.length() && j>=pattern.length()){
return true;
}
if (j>=pattern.length()) return false;
// j is the end of pattern. It can be used to cover all chars in text
if(j == pattern.length()-1 && pattern.charAt(j) == '*') return true;
if(pattern.charAt(j) == '*'){
boolean dontUseStar = dfs(i, j+1); // don't use star
if (dontUseStar) {
map.put(curr, true);
return true;
}
// use star
// find next char that is after * in pattern
char afterStarChar = pattern.charAt(j+1); // since we check if j is the last char in a if condition above, j+1 will not be out of bound.
int afterStarIndex = j+1;
while(afterStarIndex<pattern.length() && pattern.charAt(afterStarIndex)=='*'){
// combine all *s that appears continuously into 1 *
afterStarChar = pattern.charAt(afterStarIndex);
afterStarIndex++;
}
// We won't know how much chars to skip in text and assume
// that * cover it, so that we can start comparing the remaining
// char with ?
// Hence, here we just try out every single position in text
if (afterStarChar == '?') {
int start = i;
while(start<text.length()){
if (dfs(start, afterStarIndex)){
map.put(curr, true);
return true;
}
start++;
}
map.put(curr, false);
return false;
}
// For the cases where the next char after * is not ?
// Similarly, we don't know how many chars that * can cover until
// the next char that matches 'afterStartChar'. So we use while loop.
// eg, afterStartChar = c and text is *cbadcb. We check 2 c.
while(i<text.length()){
while(i<text.length() && text.charAt(i)!=afterStarChar){
i++;
}
// find next char in text that is the same as afterStarChar
if (dfs(i, j+1)){ // use star
map.put(curr, true);
return true;
}
i++;
}
}
boolean match = i < text.length() && (text.charAt(i) == pattern.charAt(j) || pattern.charAt(j) == '?');
if(match){
boolean ans = dfs(i+1, j+1); // curr char matches
if (ans){
map.put(curr, true);
return true;
}
}
map.put(curr, false);
return false;
}
}
// If you don't understnand the logic at first glance, delete all the code relating to
// map...that's the cache..can ignore first.The solution above was written by me…it is quite complicated and hard to understand. I don’t even know what is the complexity.
Editorial’s Answer
class Solution {
public boolean isMatch(String s, String p) {
int sLen = s.length(), pLen = p.length();
// base cases
if (p.equals(s)) {
return true;
}
if (pLen > 0 && p.chars().allMatch(c -> c == '*')) {
return true;
}
if (p.isEmpty() || s.isEmpty()) {
return false;
}
// init all matrix except [0][0] element as False
boolean[][] d = new boolean[pLen + 1][sLen + 1];
d[0][0] = true;
// DP compute
for (int pIdx = 1; pIdx < pLen + 1; pIdx++) {
// the current character in the pattern is '*'
if (p.charAt(pIdx - 1) == '*') {
int sIdx = 1;
// d[p_idx - 1][s_idx - 1] is a string-pattern match
// on the previous step, i.e. one character before.
// Find the first idx in string with the previous math.
while ((!d[pIdx - 1][sIdx - 1]) && (sIdx < sLen + 1)) {
sIdx++;
}
// If (string) matches (pattern),
// when (string) matches (pattern)* as well
d[pIdx][sIdx - 1] = d[pIdx - 1][sIdx - 1];
// If (string) matches (pattern),
// when (string)(whatever_characters) matches (pattern)* as well
while (sIdx < sLen + 1) {
d[pIdx][sIdx++] = true;
}
// the current character in the pattern is '?'
} else if (p.charAt(pIdx - 1) == '?') {
for (int sIdx = 1; sIdx < sLen + 1; sIdx++) {
d[pIdx][sIdx] = d[pIdx - 1][sIdx - 1];
}
// the current character in the pattern is not '*' or '?'
} else {
for (int sIdx = 1; sIdx < sLen + 1; sIdx++) {
// Match is possible if there is a previous match
// and current characters are the same
d[pIdx][sIdx] = d[pIdx - 1][sIdx - 1] &&
(p.charAt(pIdx - 1) == s.charAt(sIdx - 1));
}
}
}
return d[pLen][sLen];
}
}67. Add Binary
Given two binary strings a and b, return their sum as a binary string.
Example 1:
Input: a = "11", b = "1"
Output: "100"Example 2:
Input: a = "1010", b = "1011"
Output: "10101"class Solution {
public String addBinary(String a, String b) {
String result = "";
int indexA = a.length()-1;
int indexB = b.length()-1;
int bringOver = 0;
while(indexA>=0 && indexB>=0){
int curr = bringOver + (a.charAt(indexA)-'0') + (b.charAt(indexB)-'0');
int toAdd = curr %2;
bringOver = curr/2;
result= String.valueOf(toAdd) + result;
indexA--;
indexB--;
}
while(indexA>=0){
int curr = bringOver + (a.charAt(indexA)-'0');
int toAdd = curr %2;
bringOver = curr/2;
result= String.valueOf(toAdd) + result;
indexA--;
}
while(indexB>=0){
int curr = bringOver + (b.charAt(indexB)-'0');
int toAdd = curr %2;
bringOver = curr/2;
result= String.valueOf(toAdd) + result;
indexB--;
}
result = String.valueOf(bringOver) +result;
String trimmed = "";
// trim all preceding 0s
int index = 0;
while(index<result.length()){
if(result.charAt(index) != '0'){
trimmed = result.substring(index);
break;
}
index++;
}
return trimmed.length() == 0? "0": trimmed;
}
}2275. Largest Combination With Bitwise AND Greater Than Zero
The bitwise AND of an array nums is the bitwise AND of all integers in nums.
- For example, for
nums = [1, 5, 3], the bitwise AND is equal to1 & 5 & 3 = 1. - Also, for
nums = [7], the bitwise AND is7.
You are given an array of positive integers candidates. Evaluate the bitwise AND of every combination of numbers of candidates. Each number in candidates may only be used once in each combination.
Return the size of the largest combination of candidates with a bitwise AND greater than 0.
Example 1:
Input: candidates = [16,17,71,62,12,24,14]
Output: 4
Explanation: The combination [16,17,62,24] has a bitwise AND of 16 & 17 & 62 & 24 = 16 > 0.
The size of the combination is 4.
It can be shown that no combination with a size greater than 4 has a bitwise AND greater than 0.
Note that more than one combination may have the largest size.
For example, the combination [62,12,24,14] has a bitwise AND of 62 & 12 & 24 & 14 = 8 > 0.Example 2:
Input: candidates = [8,8]
Output: 2
Explanation: The largest combination [8,8] has a bitwise AND of 8 & 8 = 8 > 0.
The size of the combination is 2, so we return 2.class Solution {
public int largestCombination(int[] A) {
int res = 0, cur = 0;
for (int i = 0; i < 30; ++i) {
cur = 0;
for (int a : A)
cur += a >> i & 1;
res = Math.max(res, cur);
}
return res;
}
}The requirement is: Return the size of the largest combination of candidates with a bitwise AND greater than 0.
We just need to convert every number in A into their binary form.
For each bit position, we need to compare the bit from every number. As long as all the bits from every number is a 1, their combination will become a 1. And hence, the value will be greater than 0.
Youtube: https://www.youtube.com/watch?v=OHi8duTs3ec&ab_channel=%5BCE%5DCodeEngineering
a>>i & 1 is a bitwise operation that extracts the i-th bit from the number a and performs a bitwise AND operation with 1.
a >> i: This performs a right shift operation on the variable a by i bits. It effectively moves the bits of a to the right by i positions. For example, if a is 9 (binary: 1001) and i is 2, a >> i would be 2 (binary: 0010).
The next 3 questions are from a coding test.
Missing Stock Prices
https://www.hackerrank.com/challenges/missing-stock-prices/problem
A time series of a stock’s highest price during a trading day (at the New York Stock Exchange), is provided to you. In each test case, the day’s highest prices is missing for certain days. By analyzing the data, try to identify the missing price for those particular days.
Input Format
The first line contains an integer N, which is the number of rows of data to follow.
This is followed by N rows of data, each of which contains a time-stamp in the first column and the day’s highest price for the stock in the second column. There is a tab delimiter between the two columns of data.
There are exactly twenty rows in each input file, where the day’s highest price is missing. The missing prices are marked as “Missing_1”, “Missing_2” ..”Missing_20". These missing records have been randomly dispersed in the rows of data.
Output Format
The output should contain exactly twenty rows, each containg your predicted value, for each of the missing values (Missing_1, Missing_2 … Missing_20) in that order.
Sample Input
250
1/3/2012 16:00:00 Missing_1
1/4/2012 16:00:00 27.47
1/5/2012 16:00:00 27.728
1/6/2012 16:00:00 28.19
1/9/2012 16:00:00 28.1
1/10/2012 16:00:00 28.15
....
....
....
12/13/2012 16:00:00 27.52
12/14/2012 16:00:00 Missing_19
12/17/2012 16:00:00 27.215
12/18/2012 16:00:00 27.63
12/19/2012 16:00:00 27.73
12/20/2012 16:00:00 Missing_20
12/21/2012 16:00:00 27.49
12/24/2012 13:00:00 27.25
12/26/2012 16:00:00 27.2
12/27/2012 16:00:00 27.09
12/28/2012 16:00:00 26.9
12/31/2012 16:00:00 26.77Sample Output
26.96
31.98
32.69
32.41
32.32
30.5
29.18
30.8
30.46
30.63
30.96
30.4
28.2
28.2
27.3
27.1666
27.58
26.82
27.13
27.68import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;
class Result {
/*
* Complete the 'calcMissing' function below.
*
* The function accepts STRING_ARRAY readings as parameter.
*/
public static void calcMissing(List<String> readings) {
// Write your code here
int numMissingValues = 20;
Info[] data = new Info[readings.size()-numMissingValues];
int[] missingIndex = new int[numMissingValues];
int ipP = 0;
int mP = 0;
for(int i=0; i<readings.size(); i++){
String[] line = readings.get(i).split("\\t");
String value = line[line.length-1];
if(value.startsWith("Missing")){
missingIndex[mP++] = i;
}else{
data[ipP++] = new Info(Double.parseDouble(value), i);
}
}
for(int i=0; i<numMissingValues; i++){
double m = 0.0;
double b = 0.0;
// If the missing index is before the first available data point, assume a linear relationship between the first and second data points. Calculate the slope (m) and intercept (b) of the line connecting these two points and uses them to predict the missing value.
if(missingIndex[i]<data[0].index){
m = (data[1].dataPoint-data[0].dataPoint)/(data[1].index-data[0].index);
b = data[0].dataPoint-m*data[0].index;
} // Similarly, if the missing index is after the last available point, assume linear relationship....
else if(missingIndex[i]>data[data.length-1].index){
double x0 = data[data.length-1].index;
double x1 = data[data.length-2].index;
double y0 = data[data.length-1].dataPoint;
double y1 = data[data.length-2].dataPoint;
m = (y1-y0)/(x1-x0);
b = y0-m*x0;
}
else{
// Find the two closest data points and calculate the slope and intercept of the line connecting them.
// Increment temp until we find a data index that is greater than the missing index.
// At that point, temp represents the index of the data point that comes after the missing index.
int temp = 0;
while(missingIndex[i]>data[temp].index){
temp++;
}
double x0 = data[temp-1].index;
double x1 = data[temp].index;
double y0 = data[temp-1].dataPoint;
double y1 = data[temp].dataPoint;
m = (y1-y0)/(x1-x0);
b = y0-m*x0;
}
double x = missingIndex[i];
double y = m*x + b;
System.out.println(y);
}
}
public static class Info {
double dataPoint;
int index;
public Info(double dataPoint, int index){
this.dataPoint = dataPoint;
this.index = index;
}
}
}
public class Solution {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
int readingsCount = Integer.parseInt(bufferedReader.readLine().trim());
List<String> readings = IntStream.range(0, readingsCount).mapToObj(i -> {
try {
return bufferedReader.readLine();
} catch (IOException ex) {
throw new RuntimeException(ex);
}
})
.collect(toList());
Result.calcMissing(readings);
bufferedReader.close();
}
}
/*
* Complete the 'maximum_path' function below.
*
* The function is expected to return an INTEGER.
* The function accepts INTEGER_ARRAY node_values as parameter.
*/
public static int maximum_path(List<Integer> node_values) {
int n = node_values.size();
int levels = (int) Math.sqrt(2 * n);
int[][] pyramid = new int[levels][levels];
int index = 0;
for (int i = 0; i < levels; i++) {
for (int j = 0; j <= i; j++) {
pyramid[i][j] = node_values.get(index);
index++;
}
}
for (int i = levels - 2; i >= 0; i--) {
for (int j = 0; j <= i; j++) {
pyramid[i][j] += Math.max(pyramid[i + 1][j], pyramid[i + 1][j + 1]);
}
}
return pyramid[0][0];
}
class Result {
/*
* Complete the 'valuation' function below.
*
* The function is expected to return a LONG_INTEGER.
* The function accepts following parameters:
* 1. LONG_INTEGER reqArea
* 2. LONG_INTEGER_ARRAY area
* 3. LONG_INTEGER_ARRAY price
*/
public static long valuation(long reqArea, List<Long> area, List<Long> price) {
HashMap<Long, List<PriceIndex>> areaToPrices = new HashMap<>();
HashMap<Long, Long> areaToTotalPrice = new HashMap<>();
createAreaToPricesMap(area, price, areaToPrices, areaToTotalPrice);
HashSet<Integer> removed = removeOutliers(area, price, areaToPrices, areaToTotalPrice);
List<Info> newList = calculateNewList(areaToPrices, removed, areaToTotalPrice);
return calculateValuation(reqArea, newList);
}
public static HashMap<Long, List<PriceIndex>> createAreaToPricesMap(List<Long> area, List<Long> price, HashMap<Long, List<PriceIndex>> areaToPrices, HashMap<Long, Long> areaToTotalPrice) {
for (int i = 0; i < area.size(); i++) {
Long currArea = area.get(i);
Long currPrice = price.get(i);
if (areaToPrices.containsKey(currArea)) {
List<PriceIndex> otherPrices = areaToPrices.get(currArea);
otherPrices.add(new PriceIndex(currPrice, i));
areaToPrices.put(currArea, otherPrices);
Long sum = areaToTotalPrice.get(currArea);
sum += currPrice;
areaToTotalPrice.put(currArea, sum);
} else {
List<PriceIndex> toAdd = new LinkedList<>();
toAdd.add(new PriceIndex(currPrice, i));
areaToPrices.put(currArea, toAdd);
areaToTotalPrice.put(currArea, currPrice);
}
}
return areaToPrices;
}
public static HashSet<Integer> removeOutliers(List<Long> area, List<Long> price, HashMap<Long, List<PriceIndex>> areaToPrices, HashMap<Long, Long> areaToTotalPrice) {
HashSet<Integer> removed = new HashSet<>();
for (int i = 0; i < area.size(); i++) {
Long currArea = area.get(i);
Long currPrice = price.get(i);
if (areaToPrices.get(currArea).size() == 1) {
// This is the unique area..no other houses of the same size
continue;
}
Long othersMean = (areaToTotalPrice.get(currArea) - currPrice) / (areaToPrices.get(currArea).size() - 1);
// Just trying to trim areas list so we can compute variance
List<Long> otherAreas = new LinkedList<>();
boolean notRemoved = true;
for (PriceIndex o : areaToPrices.get(currArea)) {
if (notRemoved && o.getIndex() == i) {
notRemoved = false; // exclude current index
continue;
}
otherAreas.add(o.getPrice());
}
Long variance = calculateVariance(otherAreas, othersMean);
double standardDeviation = Math.sqrt(variance);
if (Math.abs(currPrice - othersMean) > (3 * standardDeviation)) {
// is outlier
removed.add(i);
}
}
return removed;
}
public static List<Info> calculateNewList(HashMap<Long, List<PriceIndex>> areaToPrices, HashSet<Integer> removed, HashMap<Long, Long> areaToTotalPrice ) {
List<Info> newList = new LinkedList<>();
for (Map.Entry<Long, List<PriceIndex>> entry : areaToPrices.entrySet()) {
long newArea = entry.getKey();
List<PriceIndex> houses = entry.getValue();
long totalPrice = areaToTotalPrice.get(newArea);
int count = houses.size();
// Remove outliers
for (PriceIndex pi : houses) {
if (removed.contains(pi.getIndex())) {
totalPrice -= pi.getPrice();
count--;
}
}
long totalA = (long) ((long) newArea * (long) count);
double avg = (double) totalPrice / (double) totalA;
if (count > 0) {
newList.add(new Info(newArea, avg, count));
}
}
return newList;
}
public static long calculateValuation(long reqArea, List<Info> newList) {
// find the nearest house to reqArea
if (newList.size() == 1) {
return fixResult(newList.get(0).price * reqArea);
}
// sort
Collections.sort(newList, Comparator.comparingLong(Info::getArea));
int leftIndex = findLeftIndex(newList, reqArea);
if (newList.get(leftIndex).area == reqArea) {
return fixResult((double) newList.get(leftIndex).price * (double) reqArea);
}
int rightIndex = leftIndex + 1;
if (leftIndex != -1 && rightIndex < newList.size()) {
double base = newList.get(leftIndex).getPriceForArea();
double diffInPrice = newList.get(rightIndex).getPriceForArea() - base;
double diffInArea = newList.get(rightIndex).area - newList.get(leftIndex).area;
double diffInAreaWithCurr = reqArea - newList.get(leftIndex).area;
return fixResult(base + (diffInPrice / diffInArea) * diffInAreaWithCurr);
}
// Extrapolate
int lastIndex = newList.size() - 1;
double base = newList.get(lastIndex).getPriceForArea();
int secondLastIndex = lastIndex - 1;
double hi = (reqArea - newList.get(lastIndex).area) * ((newList.get(lastIndex).getPriceForArea()) - (newList.get(secondLastIndex).getPriceForArea())) / ((newList.get(lastIndex).area - newList.get(secondLastIndex).area));
return fixResult(base + hi);
}
public static class Info{
long area;
double price; // avg per sqr feet
int count; // num of houses with this area
public Info(long area, double price, int count){
this.area = area;
this.price = price;
this.count = count;
}
public long getArea() {
return area;
}
public double getPrice() {
return price;
}
public String toString(){
return area + " " + price;
}
public double getPriceForArea(){
return price * (double) area;
}
}
public static class PriceIndex{
long price;
int index;
public PriceIndex(long price, int index){
this.price = price;
this.index = index;
}
public long getPrice() {
return price;
}
public int getIndex() {
return index;
}
}
private static int findLeftIndex(List<Info> newArea, long reqArea) {
int leftIndex = -1;
int size = newArea.size();
for (int i = 0; i < size; i++) {
if (newArea.get(i).area <= reqArea) {
leftIndex = i;
} else {
break;
}
}
return leftIndex;
}
public static Long calculateMean(List<Long> numbers) {
long sum = 0;
for (Long num : numbers) {
sum += num;
}
return sum / numbers.size();
}
public static long calculateVariance(List<Long> numbers, Long mean) {
long sumSquaredDiff = 0;
for (long num : numbers) {
long diff = num - mean;
sumSquaredDiff += diff * diff;
}
return sumSquaredDiff / numbers.size();
}
public static long fixResult(double result){
if(result<1000){
return 1000;
}
if(result>1000000){
return 1000000;
}
return (long) result;
}
}The solution above only solves 9/12 test cases. I spent the whole afternoon…
Binary Search
875. Koko Eating Bananas
Koko loves to eat bananas. There are n piles of bananas, the ith pile has piles[i] bananas. The guards have gone and will come back in h hours.
Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour.
Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.
Return the minimum integer k such that she can eat all the bananas within h hours.
Example 1:
Input: piles = [3,6,7,11], h = 8
Output: 4Example 2:
Input: piles = [30,11,23,4,20], h = 5
Output: 30Example 3:
Input: piles = [30,11,23,4,20], h = 6
Output: 23class Solution {
public:
int minEatingSpeed(vector<int>& piles, int h) {
int left = 1, right = *max_element(piles.begin(), piles.end());
while(left < right){
int middle = (left + right) / 2;
int hourSpent = 0;
for(int pile: piles){
hourSpent += pile/middle+(pile % middle != 0);
}
if(hourSpent > h){
left = middle + 1; // incre the speed
} else {
right = middle;
}
}
return right;
}
};In C++, when a boolean value is used in a numeric context, true is treated as 1 and false is treated as 0. This is known as implicit boolean-to-integer conversion.
The brute force way is to start from speed = 1 and then keep incrementing the speed by 1 and check if we can finish all the piles.
However, this is inefficient, hence we will use binary search to help.
Let the lower bound be 1, the minimum possible eating speed since there is no speed slower than 1. The upper bound will be the maximum eating speed, that is the maximum number of bananas in a pile. For instance, if the piles are [3,5,7,9], then 999 is the maximum number of bananas in a single pile, we can set the upper boundary as 999. Because Koko can eat every pile within 1 hour with a speed of 999, or any other faster speed, 999 is thus guaranteed to be a workable value.
Let n be the length of the input array piles and m be the maximum number of bananas in a single pile from piles.
Time complexity: O(n⋅logm)
- The initial search space is from 1 to m, it takes logm comparisons to reduce the search space to 1.
- For each eating speed middle, we traverse the array and calculate the overall time Koko spends, which takes O(n) for each traversal.
- To sum up, the time complexity is O(n⋅logm).
Space complexity: O(1)
- For each eating speed middle, we iterate over the array and calculate the total hours Koko spends, which costs constant space.
- Therefore, the overall space complexity is O(1)
Refer to https://liverungrow.medium.com/binary-search-a26e660a2bd
For more on how to identify questions requiring binary search algorithms, as well as the approach to solving them.
291 Word Pattern II
Given a pattern and a string s, return true if s matches the pattern.
A string s matches a pattern if there is some bijective mapping of single characters to strings such that if each character in pattern is replaced by the string it maps to, then the resulting string is s. A bijective mapping means that no two characters map to the same string, and no character maps to two different strings.
Example 1:
Input: pattern = "abab", s = "redblueredblue"
Output: true
Explanation: One possible mapping is as follows:
'a' -> "red"
'b' -> "blue"Example 2:
Input: pattern = "aaaa", s = "asdasdasdasd"
Output: true
Explanation: One possible mapping is as follows:
'a' -> "asd"Example 3:
Input: pattern = "aabb", s = "xyzabcxzyabc"
Output: falseclass Solution {
public:
unordered_map<char, string> map;
unordered_set<string> visitedSubStrings;
bool wordPatternMatch(string pattern, string s) {
// brute force..select index in s to slice
// for each char...
// a -> 0...s.length()
// for each try,
// find match in string?
if(pattern.empty()) return s.empty();
char currChar = pattern[0];
if(map.count(currChar) > 0){
string mappedString = map[currChar];
if(s.length() < mappedString.length() || s.substr(0, mappedString.length()) != (mappedString)) return false;
return wordPatternMatch(pattern.substr(1), s.substr(mappedString.length()));
} else {
for(int i=1; i<=s.length(); i++){
// try matching curr pattern char with any num of chars in s
string currSubstring = s.substr(0, i);
if(visitedSubStrings.count(currSubstring) > 0) continue;
map[currChar] = currSubstring;
visitedSubStrings.insert(currSubstring);
if(wordPatternMatch(pattern.substr(1), s.substr(i))) return true;
visitedSubStrings.erase(currSubstring);
map.erase(currChar);
}
}
return false;
}
};1 char -> a few chars (We don’t know how many). Different from 290 qns.
290. Word Pattern
Given a pattern and a string s, find if s follows the same pattern.
Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in s.
Example 1:
Input: pattern = "abba", s = "dog cat cat dog"
Output: trueExample 2:
Input: pattern = "abba", s = "dog cat cat fish"
Output: falseExample 3:
Input: pattern = "aaaa", s = "dog cat cat dog"
Output: falseclass Solution {
public:
bool wordPattern(string pattern, string s) {
string token;
unordered_map<char, string> map;
unordered_map<string, char> strmap;
int i=0;
istringstream iss(s);
while(getline(iss, token, ' ')){
if(map.count(pattern[i]) > 0){
string matchingStr = map[pattern[i]];
if(token != matchingStr) return false;
} else if(strmap.count(token) > 0){
char pat = strmap[token];
if(pattern[i] != pat) return false;
} else {
map[pattern[i]]=token;
strmap[token]=pattern[i];
}
i++;
}
return i == pattern.length(); // eg, pattern "jquery", s "jquery"
}
};1 char -> 1 word
890. Find and Replace Pattern
Given a list of strings words and a string pattern, return a list of words[i] that match pattern. You may return the answer in any order.
A word matches the pattern if there exists a permutation of letters p so that after replacing every letter x in the pattern with p(x), we get the desired word.
Recall that a permutation of letters is a bijection from letters to letters: every letter maps to another letter, and no two letters map to the same letter.
Example 1:
Input: words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"
Output: ["mee","aqq"]
Explanation: "mee" matches the pattern because there is a permutation {a -> m, b -> e, ...}.
"ccc" does not match the pattern because {a -> c, b -> c, ...} is not a permutation, since a and b map to the same letter.Example 2:
Input: words = ["a","b","c"], pattern = "a"
Output: ["a","b","c"]class Solution {
public:
vector<string> findAndReplacePattern(vector<string>& words, string pattern) {
vector<string> result;
for(string word: words){
if(wordPatternMatch(pattern, word)){
result.push_back(word);
}
}
return result;
}
bool wordPatternMatch(string pattern, string word) {
unordered_map<char, char> m1;
unordered_map<char, char> m2;
for (int i = 0; i < word.length(); ++i) {
char w = word[i];
char p = pattern[i];
if (m1.count(w) == 0) m1[w] = p;
if (m2.count(p) ==0) m2[p] = w;
if (m1[w] != p || m2[p] != w)
return false;
}
return true;
}
};
1 char -> 1 char -> Similar to Leetcode 290. But this time, our value can be a single char.
456. 132 Pattern
Given an array of n integers nums, a 132 pattern is a subsequence of three integers nums[i], nums[j] and nums[k] such that i < j < k and nums[i] < nums[k] < nums[j].
Return true if there is a 132 pattern in nums, otherwise, return false.
Example 1:
Input: nums = [1,2,3,4]
Output: false
Explanation: There is no 132 pattern in the sequence.Example 2:
Input: nums = [3,1,4,2]
Output: true
Explanation: There is a 132 pattern in the sequence: [1, 4, 2].Example 3:
Input: nums = [-1,3,2,0]
Output: true
Explanation: There are three 132 patterns in the sequence: [-1, 3, 2], [-1, 3, 0] and [-1, 2, 0].class Solution {
public:
bool find132pattern(vector<int>& nums) {
if(nums.size()<3) return false;
stack<int> maxRight;
vector<int> minLeft;
minLeft.push_back(nums[0]);
for(int i=1; i<nums.size(); i++){
minLeft.push_back(min(minLeft[i-1], nums[i]));
}
for(int i=nums.size()-1; i>0; i--){
if(nums[i] == minLeft[i]) continue;
while(!maxRight.empty() && maxRight.top() <= minLeft[i]){
maxRight.pop();
}
if(!maxRight.empty() && maxRight.top()<nums[i]){
// there is a val on the right of curr that is bigger than minLeft
// this val is also smaller than curr
return true;
}
maxRight.push(nums[i]);
}
return false;
}
};This algo is very un-intuitive.
- store all the min value in an arr. arr[i] represents the min value to it’s left
- iterate from right to left.
Maintain a max value stack. It contains all the values that are bigger than the current min value array arr[i]. The value needs to be at least bigger than the minimum value of the current number. This is to fulfill the first condition. -> We ensure this by doing the first while loop check.
Then, check if the stack topmost value is smaller than current number. If yes, return true.
Otherwise, add curr value to stack.
459. Repeated Substring Pattern
Given a string s, check if it can be constructed by taking a substring of it and appending multiple copies of the substring together.
Example 1:
Input: s = "abab"
Output: true
Explanation: It is the substring "ab" twice.Example 2:
Input: s = "aba"
Output: falseExample 3:
Input: s = "abcabcabcabc"
Output: true
Explanation: It is the substring "abc" four times or the substring "abcabc" twice.class Solution {
public:
bool repeatedSubstringPattern(string s) {
char firstChar = s[0];
int end=1;
while(end<s.length()){
string substring = s.substr(0, end);
if(firstChar==s[end] && test(s.substr(end), substring)){
return true;
}
end++;
}
return false;
}
bool test(string s, string substring){
int window = substring.length();
if(s.length() % window != 0) return false;
int start=0;
while(start+window<=s.length()){
string currWindowString = s.substr(start, window);
// the 2nd param of substr is the length not end index...
if(currWindowString != substring) return false;
start+=window;
}
return true;
}
};118. Pascal’s Triangle
Given an integer numRows, return the first numRows of Pascal's triangle.
In Pascal’s triangle, each number is the sum of the two numbers directly above it as shown:
Example 1:
Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]Example 2:
Input: numRows = 1
Output: [[1]]class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> result;
for(int i=1; i<=numRows; i++){
vector<int> row;
for(int j=1; j<=i; j++){
if(j==1 || j==i){
row.push_back(1);
} else {
// the loop is indexed from 1, so we need to do additional -1 below.
row.push_back(result[i-2][j-2]+result[i-2][j-1]);
}
}
result.push_back(row);
}
return result;
}
};119. Pascal’s Triangle II
Given an integer rowIndex, return the rowIndexth (0-indexed) row of the Pascal's triangle.
In Pascal’s triangle, each number is the sum of the two numbers directly above it as shown:
Example 1:
Input: rowIndex = 3
Output: [1,3,3,1]Example 2:
Input: rowIndex = 0
Output: [1]Example 3:
Input: rowIndex = 1
Output: [1,1]class Solution {
public:
vector<int> getRow(int rowIndex) {
vector<int> res;
res.push_back(1);
for(int i=0; i<rowIndex; i++){
for(int j=res.size()-1; j>=0; j--){
if(j-1>=0){
res[j]+=res[j-1];
}
}
res.push_back(1); // always add 1 to the end of each row
}
return res;
}
};The idea is to build upon previous row. Add the previous value of res[j] to res[j+1] to get the new value of res[j+1] in the current row.
739. Daily Temperatures
Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.
Example 1:
Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]Example 2:
Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]Example 3:
Input: temperatures = [30,60,90]
Output: [1,1,0]class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int[] result = new int[temperatures.length];
Stack<Info> s = new Stack<>();
s.push(new Info(temperatures.length-1, temperatures[temperatures.length-1]));
for(int i=temperatures.length-2; i>=0; i--){
while(s.size() > 0 && s.peek().temp<=temperatures[i]) {
s.pop();
}
if(s.size() != 0){
result[i]=s.peek().index-i;
}
s.push(new Info(i, temperatures[i]));
}
return result;
}
}
public class Info {
int index;
int temp;
public Info(int index, int temp){
this.index = index;
this.temp = temp;
}
}1668. Maximum Repeating Substring
For a string sequence, a string word is k-repeating if word concatenated k times is a substring of sequence. The word's maximum k-repeating value is the highest value k where word is k-repeating in sequence. If word is not a substring of sequence, word's maximum k-repeating value is 0.
Given strings sequence and word, return the maximum k-repeating value of word in sequence.
Example 1:
Input: sequence = "ababc", word = "ab"
Output: 2
Explanation: "abab" is a substring in "ababc".Example 2:
Input: sequence = "ababc", word = "ba"
Output: 1
Explanation: "ba" is a substring in "ababc". "baba" is not a substring in "ababc".Example 3:
Input: sequence = "ababc", word = "ac"
Output: 0
Explanation: "ac" is not a substring in "ababc".Need to understand the question…the word must be concatenated continuously…
class Solution {
public:
int maxRepeating(string sequence, string word) {
int count=0;
string temp=word;
while(sequence.find(temp)!=string::npos)
{
count++;
temp+=word;
}
return count;
}
};238. Product of Array Except Self
Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
You must write an algorithm that runs in O(n) time and without using the division operation.
Example 1:
Input: nums = [1,2,3,4]
Output: [24,12,8,6]Example 2:
Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int zeroCount = 0;
long total = 1; // impt
for(int n: nums){
if(n==0){
zeroCount++;
continue;
}
total *= n;
}
vector<int> res;
for(int n: nums){
if(zeroCount>0 && n!=0){
res.push_back(0);
} else if(zeroCount==1 && n==0){
res.push_back(total);
} else if (zeroCount>1 && n==0){
res.push_back(0);
}else {
res.push_back(total/n);
}
}
return res;
}
};293. Flip Game
You are playing a Flip Game with your friend.
You are given a string currentState that contains only '+' and '-'. You and your friend take turns to flip two consecutive "++" into "--". The game ends when a person can no longer make a move, and therefore the other person will be the winner.
Return all possible states of the string currentState after one valid move. You may return the answer in any order. If there is no valid move, return an empty list [].
Example 1:
Input: currentState = "++++"
Output: ["--++","+--+","++--"]Example 2:
Input: currentState = "+"
Output: []class Solution {
public List<String> generatePossibleNextMoves(String currentState) {
List<String> result = new LinkedList();
for(int i=0; i<=currentState.length()-2; i++){
if(currentState.substring(i, i+2).equals("++")){
String newString = currentState.substring(0, i)+"--"+currentState.substring(i+2);
result.add(newString);
}
}
return result;
}
}294. Flip Game II
You are playing a Flip Game with your friend.
You are given a string currentState that contains only '+' and '-'. You and your friend take turns to flip two consecutive "++" into "--". The game ends when a person can no longer make a move, and therefore the other person will be the winner.
Return true if the starting player can guarantee a win, and false otherwise.
Example 1:
Input: currentState = "++++"
Output: true
Explanation: The starting player can guarantee a win by flipping the middle "++" to become "+--+".Example 2:
Input: currentState = "+"
Output: falseclass Solution {
public boolean canWin(String s) {
if (s == null || s.length() < 2) {
return false;
}
for (int i = 0; i < s.length() - 1; i++) {
if(s.substring(i, i+2).equals("++")){
String newString = s.substring(0, i)+"--"+s.substring(i+2);
if (!canWin(newString)) {
return true;
}
}
}
return false;
}
}
// Try every scenario and see if the opponent can win..For the time complexity
let’s say the length of the input string s is n, there are at most n - 1 ways to replace "++" to "--" (imagine s is all "+++..."), once we replace one "++", there are at most (n - 2) - 1 ways to do the replacement, it's a little bit like solving the N-Queens problem, the time complexity is (n - 1) x (n - 3) x (n - 5) x ..., so it's O(n!!)
(Copied from leetcode)
The solution is simplified from:
public class Solution {
public boolean canWin(String s) {
for(int i=0;i<s.length()-1;i++)
{
if(s.charAt(i)=='+' && s.charAt(i+1)=='+')
{
if(!canOpponentWin(s.substring(0,i)+"--"+s.substring(i+2)))
return true;
}
}
return false;
}
private boolean canOpponentWin(String s)
{
for(int i=0;i<s.length()-1;i++)
{
if(s.charAt(i)=='+' && s.charAt(i+1)=='+')
{
if(!canWin(s.substring(0,i)+"--"+s.substring(i+2)))
return true;
}
}
return false;
}
}390. Elimination Game
You have a list arr of all integers in the range [1, n] sorted in a strictly increasing order. Apply the following algorithm on arr:
- Starting from left to right, remove the first number and every other number afterward until you reach the end of the list.
- Repeat the previous step again, but this time from right to left, remove the rightmost number and every other number from the remaining numbers.
- Keep repeating the steps again, alternating left to right and right to left, until a single number remains.
Given the integer n, return the last number that remains in arr.
Example 1:
Input: n = 9
Output: 6
Explanation:
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
arr = [2, 4, 6, 8]
arr = [2, 6]
arr = [6]Example 2:
Input: n = 1
Output: 1The solution below exceeds memory.
class Solution {
public int lastRemaining(int n) {
Deque<Integer> queue = new ArrayDeque<>();
for(int i=1; i<=n; i++){
queue.addLast(i);
}
while(queue.size() != 1){
int qsize = queue.size();
Deque<Integer> newQ = new ArrayDeque<>();
int count = 0;
for(int i=0; i<qsize; i++){
int c = queue.removeFirst(); // read from left
if(count%2==1){
newQ.addLast(c);
}
count++;
}
if(newQ.size() == 1) return newQ.getFirst();
int qsize2 = newQ.size();
count = 0;
for(int i=0; i<qsize2; i++){
int c = newQ.removeLast(); // read from right
if(count%2 == 1){
queue.addFirst(c);
}
count++;
}
}
return queue.getFirst();
}
}Copied from leetcode
public int lastRemaining(int n) {
boolean left = true;
int remaining = n;
int step = 1;
int head = 1;
while (remaining > 1) {
if (left || remaining % 2 ==1) {
head = head + step;
}
remaining = remaining / 2;
step = step * 2;
left = !left;
}
return head;
}The idea is to update and record head in each turn. when the total number becomes 1, head is the only number left.
When will head be updated?
- if we move from left
- if we move from right and the total remaining number % 2 == 1
like 2 4 6 8 10, we move from 10, we will take out 10, 6 and 2, head is deleted and move to 4
like 2 4 6 8 10 12, we move from 12, we will take out 12, 8, 4, head is still remaining as 2
then we find a rule to update our head.
example:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
- Let us start with head = 1, left = true, step = 1 (times 2 each turn), remaining = n(24)
- we first move from left, we definitely need to move head to next position. (head = head + step)
So after first loop we will have:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 → 2 4 6 8 10 12 14 16 18 20 22 24
head = 2, left = false, step = 1 * 2 = 2, remaining = remaining / 2 = 12 - second loop, we move from right, in what situation we need to move head?
only if the remaining % 2 == 1, in this case we have 12 % 2 == 0, we don’t touch head.
so after this second loop we will have:
2 4 6 8 10 12 14 16 18 20 22 24 → 2 6 10 14 18 22
head = 2, left = true, step = 2 * 2 = 4, remaining = remaining / 2 = 6 - third loop, we move from left, move head to next position
after third loop we will have:
2 6 10 14 18 22 → 6 14 22
head = 6, left = false, step = 4 * 2 = 8, remaining = remaining / 2 = 3 - fourth loop, we move from right, NOTICE HERE:
we have remaining(3) % 2 == 1, so we know we need to move head to next position
after this loop, we will have
6 14 22 → 14
head = 14, left = true, step = 8 * 2 = 16, remaining = remaining / 2 = 1 - while loop end, return head
289. Game of Life
According to Wikipedia’s article: “The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970.”
The board is made up of an m x n grid of cells, where each cell has an initial state: live (represented by a 1) or dead (represented by a 0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):
- Any live cell with fewer than two live neighbors dies as if caused by under-population.
- Any live cell with two or three live neighbors lives on to the next generation.
- Any live cell with more than three live neighbors dies, as if by over-population.
- Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.
The next state is created by applying the above rules simultaneously to every cell in the current state, where births and deaths occur simultaneously. Given the current state of the m x n grid board, return the next state.
Example 1:
Input: board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]
Output: [[0,0,0],[1,0,1],[0,1,1],[0,1,0]]Example 2:
Input: board = [[1,1],[1,0]]
Output: [[1,1],[1,1]]class Solution {
public void gameOfLife(int[][] board) {
HashSet<Coordinate> alive = new HashSet<>();
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
int count = numOfLiveNeigh(board, i, j);
if (count == 3) {
alive.add(new Coordinate(i, j));
}
if (board[i][j] == 1 && count == 2) {
alive.add(new Coordinate(i, j));
}
}
}
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (alive.contains(new Coordinate(i, j))) {
board[i][j] = 1;
} else {
board[i][j] = 0;
}
}
}
}
public int numOfLiveNeigh(int[][] board, int row, int col){
int count = 0;
for(int i=row-1; i<=row+1; i++){
for(int j=col-1; j<=col+1; j++){
if(i==row && col==j) continue; // skip curr
if(i>=0 && i<=board.length-1 && j>=0 && j<=board[0].length-1 && board[i][j] == 1){
count++;
}
}
}
return count;
}
}
class Coordinate {
int x;
int y;
public Coordinate(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public boolean equals(Object obj) {
if (this == obj) {
return true;
}
if (obj == null || getClass() != obj.getClass()) {
return false;
}
Coordinate other = (Coordinate) obj;
return x == other.x && y == other.y;
}
@Override
public int hashCode() {
return Objects.hash(x, y);
}
}Note that we created a separate class for Coordinate because Hashset equality will compare object reference, instead of the values. We want the latter. Hence, we need to overwrite hashcode and equals.
Magic Squares
A separate YouTube video about making the minimum changes to form a magic square. The solution is to generate all possible magic squares and compare the cost of generating it to the original square. We make use of some observed special properties that a magic square should have to help in the generation of magic squares.
A 3 x 3 magic square is a 3 x 3 grid filled with distinct numbers from 1 to 9 such that each row, column, and both diagonals all have the same sum.
Given a row x col grid of integers, how many 3 x 3 "magic square" subgrids are there? (Each subgrid is contiguous).
Example 1:
Input: grid = [[4,3,8,4],[9,5,1,9],[2,7,6,2]]
Output: 1
Explanation:
The following subgrid is a 3 x 3 magic square:
while this one is not:
In total, there is only one magic square inside the given grid.Example 2:
Input: grid = [[8]]
Output: 0class Solution {
public int numMagicSquaresInside(int[][] grid) {
int count = 0;
if(grid.length<3 || grid[0].length<3) return 0;
for(int i=0; i<=grid.length-3; i++){
for(int j=0; j<=grid[0].length-3; j++){
if(isMagicSquare(grid, i, j, 3)){
count++;
}
}
}
return count;
}
private Boolean isMagicSquare(int[][] grid, int row, int col, int k){
HashSet<Integer> set = new HashSet<>();
int expectedSum = -1;
HashMap<Integer, Integer> colToSum = new HashMap<>();
for(int i=row; i<row+k; i++){
int sumOfRow= 0;
for(int j=col; j<col+k; j++){
if(set.contains(grid[i][j]) || grid[i][j] < 1 || grid[i][j]>9){
return false;
}
set.add(grid[i][j]); // row
sumOfRow+=grid[i][j]; // row
colToSum.putIfAbsent(j, 0); // col
colToSum.put(j, colToSum.get(j)+grid[i][j]); // col
}
if(expectedSum==-1){
expectedSum = sumOfRow;
}else if(expectedSum!=sumOfRow){
return false;
}
}
for(Map.Entry<Integer, Integer> entry: colToSum.entrySet()){
int colVal = entry.getKey();
int colSum = entry.getValue();
if(colSum!= expectedSum) return false;
}
// check diagonal
int sumDiag = grid[row][col]+grid[row+1][col+1]+grid[row+2][col+2];
int sumAntiDiag = grid[row][col+2]+grid[row+1][col+1]+grid[row+2][col];
return sumDiag == expectedSum && sumAntiDiag == expectedSum;
}
}1895. Largest Magic Square
A k x k magic square is a k x k grid filled with integers such that every row sum, every column sum, and both diagonal sums are all equal. The integers in the magic square do not have to be distinct. Every 1 x 1 grid is trivially a magic square.
Given an m x n integer grid, return the size (i.e., the side length k) of the largest magic square that can be found within this grid.
Example 1:
Input: grid = [[7,1,4,5,6],[2,5,1,6,4],[1,5,4,3,2],[1,2,7,3,4]]
Output: 3
Explanation: The largest magic square has a size of 3.
Every row sum, column sum, and diagonal sum of this magic square is equal to 12.
- Row sums: 5+1+6 = 5+4+3 = 2+7+3 = 12
- Column sums: 5+5+2 = 1+4+7 = 6+3+3 = 12
- Diagonal sums: 5+4+3 = 6+4+2 = 12Example 2:
Input: grid = [[5,1,3,1],[9,3,3,1],[1,3,3,8]]
Output: 2Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 501 <= grid[i][j] <= 106
class Solution {
public int largestMagicSquare(int[][] g) {
int R = g.length, C = g[0].length, rows[][] = new int[R][C + 1], cols[][] = new int[R + 1][C];
for (int i = 0; i < R; i++)
for (int j = 0; j < C; j++) {
rows[i][j + 1] = rows[i][j] + g[i][j];//cumulative sum for each row
cols[i + 1][j] = cols[i][j] + g[i][j];//cumulative sum for each column
}
for (int side = Math.min(R, C); side > 1; side--)//start with the biggest side possible
for (int i = 0; i <= R - side; i++)//check every square
for (int j = 0; j <= C - side; j++)
if (magic(g, rows, cols, i, j, side))//checks if a square with top left [i, j] and side length is magic
return side;
return 1;
}
boolean magic(int[][] g, int[][] rows, int[][] cols, int r, int c, int side) {
int sum = rows[r][c + side] - rows[r][c], d1 = 0, d2 = 0;
for (int k = 0; k < side; k++) {
d1 += g[r + k][c + k];
d2 += g[r + side - 1 - k][c + k];
if (rows[r + k][c + side] - rows[r + k][c] != sum || cols[r + side][c + k] - cols[r][c + k] != sum)//check each row and column
return false;
}
return d1 == sum && d2 == sum;//checks both diagonals
}
}Given an array of values from 1 to 100, return the missing values
Create a hashset of values from 1 to 100. Iterate through the given array and remove values from hashset one by one.
268. Missing Number
Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.
Example 1:
Input: nums = [3,0,1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.Example 2:
Input: nums = [0,1]
Output: 2
Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.Example 3:
Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
Explanation: n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.class Solution {
public int missingNumber(int[] nums) {
int[] count = new int[nums.length+1];
for(int i=0; i<nums.length; i++){
count[i]=0;
}
for(int i=0; i<nums.length; i++){
count[nums[i]]=1;
}
for(int i=0; i<nums.length; i++){
if(count[i]==0) return i;
}
return count.length-1;
}
}1356. Sort Integers by The Number of 1 Bits
You are given an integer array arr. Sort the integers in the array in ascending order by the number of 1's in their binary representation and in case of two or more integers have the same number of 1's you have to sort them in ascending order.
Return the array after sorting it.
Example 1:
Input: arr = [0,1,2,3,4,5,6,7,8]
Output: [0,1,2,4,8,3,5,6,7]
Explantion: [0] is the only integer with 0 bits.
[1,2,4,8] all have 1 bit.
[3,5,6] have 2 bits.
[7] has 3 bits.
The sorted array by bits is [0,1,2,4,8,3,5,6,7]Example 2:
Input: arr = [1024,512,256,128,64,32,16,8,4,2,1]
Output: [1,2,4,8,16,32,64,128,256,512,1024]
Explantion: All integers have 1 bit in the binary representation, you should just sort them in ascending order.class Solution {
public int[] sortByBits(int[] arr) {
int[][] curr = new int[arr.length][2];
for(int i=0; i<arr.length; i++){
curr[i][0] = arr[i];
curr[i][1] = Integer.bitCount(arr[i]);
}
Arrays.sort(curr, (a, b) -> a[1]==b[1] ? a[0]-b[0] : a[1]-b[1]);
for(int i=0; i<arr.length; i++){
arr[i] = curr[i][0];
}
return arr;
}
}1481. Least Number of Unique Integers after K Removals
Given an array of integers arr and an integer k. Find the least number of unique integers after removing exactly k elements.
Example 1:
Input: arr = [5,5,4], k = 1
Output: 1
Explanation: Remove the single 4, only 5 is left.Example 2:
Input: arr = [4,3,1,1,3,3,2], k = 3
Output: 2
Explanation: Remove 4, 2 and either one of the two 1s or three 3s. 1 and 3 will be left.Constraints:
1 <= arr.length <= 10^51 <= arr[i] <= 10^90 <= k <= arr.length
class Solution {
public int findLeastNumOfUniqueInts(int[] arr, int k) {
Map<Integer, Integer> map = new HashMap<>();
// remove those elements with fewer counts
for(int i=0; i<arr.length; i++){
map.putIfAbsent(arr[i], 0);
int count = map.get(arr[i]);
map.put(arr[i], count+1);
}
// sort by count
// remove those vals with lowest count
// This strategy will allow us to remove as many unique number as possible
int size = map.size();
int count[] = new int[size];
int j = 0;
for(Map.Entry<Integer, Integer> entry: map.entrySet()){
count[j++] = entry.getValue();
}
Arrays.sort(count);
int countIndex=0;
do{
k-=count[countIndex];
if(k<0){
break;
}
countIndex++;
} while(k>0);
return size-countIndex;
}
}1529. Minimum Suffix Flips
You are given a 0-indexed binary string target of length n. You have another binary string s of length n that is initially set to all zeros. You want to make s equal to target.
In one operation, you can pick an index i where 0 <= i < n and flip all bits in the inclusive range [i, n - 1]. Flip means changing '0' to '1' and '1' to '0'.
Return the minimum number of operations needed to make s equal to target.
Example 1:
Input: target = "10111"
Output: 3
Explanation: Initially, s = "00000".
Choose index i = 2: "00000" -> "00111"
Choose index i = 0: "00111" -> "11000"
Choose index i = 1: "11000" -> "10111"
We need at least 3 flip operations to form target.Example 2:
Input: target = "101"
Output: 3
Explanation: Initially, s = "000".
Choose index i = 0: "000" -> "111"
Choose index i = 1: "111" -> "100"
Choose index i = 2: "100" -> "101"
We need at least 3 flip operations to form target.Example 3:
Input: target = "00000"
Output: 0
Explanation: We do not need any operations since the initial s already equals target.// time limit exceeded
class Solution {
public int minFlips(String target) {
// find num of sections
// flip values from left to right...
int start=0;
int end=0;
int count=0;
char[] current = new char[target.length()];
Arrays.fill(current, '0');
while(end<target.length()){
char targetChar = target.charAt(start);
char currentChar = current[start];
if(targetChar == currentChar) {
start++;
end++;
continue;
}
while(end<target.length() && target.charAt(end)==target.charAt(start)){
current[end] = current[end] == '0' ? '1' : '0';
end++;
}
// do flip
for(int i=end; i<current.length; i++){
current[i] = current[i] == '0' ? '1' : '0';
}
start=end;
count++;
}
return count;
}
}O(n) solution
class Solution {
public int minFlips(String target) {
char status = '0';
int flips = 0;
for(int i=0; i<target.length(); i++){
if(target.charAt(i) != status){
flips++;
status = status == '0' ? '1' : '0';
}
}
return flips;
}
}2038. Remove Colored Pieces if Both Neighbors are the Same Color
There are n pieces arranged in a line, and each piece is colored either by 'A' or by 'B'. You are given a string colors of length n where colors[i] is the color of the ith piece.
Alice and Bob are playing a game where they take alternating turns removing pieces from the line. In this game, Alice moves first.
- Alice is only allowed to remove a piece colored
'A'if both its neighbors are also colored'A'. She is not allowed to remove pieces that are colored'B'. - Bob is only allowed to remove a piece colored
'B'if both its neighbors are also colored'B'. He is not allowed to remove pieces that are colored'A'. - Alice and Bob cannot remove pieces from the edge of the line.
- If a player cannot make a move on their turn, that player loses and the other player wins.
Assuming Alice and Bob play optimally, return true if Alice wins, or return false if Bob wins.
Example 1:
Input: colors = "AAABABB"
Output: true
Explanation:
AAABABB -> AABABB
Alice moves first.
She removes the second 'A' from the left since that is the only 'A' whose neighbors are both 'A'.Now it's Bob's turn.
Bob cannot make a move on his turn since there are no 'B's whose neighbors are both 'B'.
Thus, Alice wins, so return true.Example 2:
Input: colors = "AA"
Output: false
Explanation:
Alice has her turn first.
There are only two 'A's and both are on the edge of the line, so she cannot move on her turn.
Thus, Bob wins, so return false.Example 3:
Input: colors = "ABBBBBBBAAA"
Output: false
Explanation:
ABBBBBBBAAA -> ABBBBBBBAA
Alice moves first.
Her only option is to remove the second to last 'A' from the right.ABBBBBBBAA -> ABBBBBBAA
Next is Bob's turn.
He has many options for which 'B' piece to remove. He can pick any.On Alice's second turn, she has no more pieces that she can remove.
Thus, Bob wins, so return false.
Constraints:
1 <= colors.length <= 105colorsconsists of only the letters'A'and'B'
// time limit exceeded
class Solution {
public boolean winnerOfGame(String colors) {
boolean alice = false;
while(colors.length()>=3){
if(!alice){
if(!colors.contains("AAA")){
return false;
}
int i = colors.indexOf("AAA");
colors = colors.substring(0, i+1)+colors.substring(i+2);
} else{
if(!colors.contains("BBB")){
return true;
}
int i = colors.indexOf("BBB");
colors = colors.substring(0, i+1)+colors.substring(i+2);
}
alice = !alice;
}
return alice;
}
}Idea behind it is that you need to count the number of triplets of both A and B
int a -> number of triplets of ‘A’
int b -> number of triplets of ‘B’
if(b>=a) BOB wins else Alice wins
As Alice has to make a move first so if she wants to win there should be at least 1 more triplets of A than B
class Solution {
public boolean winnerOfGame(String colors) {
int n = colors.length();
int a = 0;
int b = 0;
for(int i=1; i<n-1; i++){
if(colors.charAt(i) == 'A' && colors.charAt(i-1)=='A' && colors.charAt(i+1) == 'A'){
a++;
} else if (colors.charAt(i) == 'B' && colors.charAt(i-1)=='B' && colors.charAt(i+1)=='B'){
b++;
}
}
if(a<=b) return false;
return true;
}
}1328. Break a Palindrome
Given a palindromic string of lowercase English letters palindrome, replace exactly one character with any lowercase English letter so that the resulting string is not a palindrome and that it is the lexicographically smallest one possible.
Return the resulting string. If there is no way to replace a character to make it not a palindrome, return an empty string.
A string a is lexicographically smaller than a string b (of the same length) if in the first position where a and b differ, a has a character strictly smaller than the corresponding character in b. For example, "abcc" is lexicographically smaller than "abcd" because the first position they differ is at the fourth character, and 'c' is smaller than 'd'.
Example 1:
Input: palindrome = "abccba"
Output: "aaccba"
Explanation: There are many ways to make "abccba" not a palindrome, such as "zbccba", "aaccba", and "abacba".
Of all the ways, "aaccba" is the lexicographically smallest.Example 2:
Input: palindrome = "a"
Output: ""
Explanation: There is no way to replace a single character to make "a" not a palindrome, so return an empty string.class Solution {
String smallest;
public String breakPalindrome(String palindrome) {
if(palindrome.length()<=1) return "";
smallest = "";
traverse(palindrome.length(), 0, palindrome);
return smallest;
}
public void traverse(int length, int index, String palindrome){
if(index==length){
return;
}
char currChar = palindrome.charAt(index);
char charToTry = 'a'; // by default, always replace the char with 'a'
if(currChar == 'a'){
charToTry = 'b';
}
String newStr = palindrome.substring(0, index)+charToTry+palindrome.substring(index+1);
if(!isStringMiddleOfOddLengthStr(index, palindrome) && (newStr.compareTo(smallest)==-1 || smallest == "")){
smallest = newStr;
}
traverse(length, index+1, palindrome);
}
private Boolean isStringMiddleOfOddLengthStr(int index, String palindrome){
if(palindrome.length()%2==0){
return false;
}
return index == palindrome.length()/2;
}
}Use recursion to try out every possibility.
The following is the solution from Leetcode editorial
class Solution {
public String breakPalindrome(String palindrome) {
int length = palindrome.length();
if (length == 1) {
return "";
}
// Strings are immutable in Java, convert it into a char array
char[] palindromeArray = palindrome.toCharArray();
for (int i = 0; i < length / 2; i++) {
if (palindromeArray[i] != 'a') {
palindromeArray[i] = 'a';
return String.valueOf(palindromeArray);
}
}
palindromeArray[length - 1] = 'b';
return String.valueOf(palindromeArray);
}
}If we observe even more closely, for every character except a, the lexicographically smallest character is a. Therefore, all the characters except a will be converted to a. Now, since we are changing the characters to a and a is the lexicographically smallest character, then among all the N conversions of the string, which will be the lexicographically smallest? It will be the one in which a is placed at the leftmost position. Thus, we need to change the first character in the string to a, and that will be the answer.
But what about the case when we cannot change any of the characters to a? For the strings made up of only character a like a or strings made up of exactly N - 1 a's (where N is the string length) and one different character in the middle, like aazaa, we need to discover another way. In the first case, there is no point in substituting aaa for another aaa. In the second case, we cannot replace z with some other character between a and y because the string will remain a palindrome. In this case, we must replace a, and the optimal character choice is b because that's the smallest among all other letters. Since the character that we are replacing the existing character with is not the smallest, we should do the swap in the rightmost position.
Finally, one last improvement to the algorithm: instead of traversing over all the characters, we can only traverse the left half as the corresponding characters in the right half will be the same.
1167. Minimum Cost to Connect Sticks
You have some number of sticks with positive integer lengths. These lengths are given as an array sticks, where sticks[i] is the length of the ith stick.
You can connect any two sticks of lengths x and y into one stick by paying a cost of x + y. You must connect all the sticks until there is only one stick remaining.
Return the minimum cost of connecting all the given sticks into one stick in this way.
Example 1:
Input: sticks = [2,4,3]
Output: 14
Explanation: You start with sticks = [2,4,3].
1. Combine sticks 2 and 3 for a cost of 2 + 3 = 5. Now you have sticks = [5,4].
2. Combine sticks 5 and 4 for a cost of 5 + 4 = 9. Now you have sticks = [9].
There is only one stick left, so you are done. The total cost is 5 + 9 = 14.Example 2:
Input: sticks = [1,8,3,5]
Output: 30
Explanation: You start with sticks = [1,8,3,5].
1. Combine sticks 1 and 3 for a cost of 1 + 3 = 4. Now you have sticks = [4,8,5].
2. Combine sticks 4 and 5 for a cost of 4 + 5 = 9. Now you have sticks = [9,8].
3. Combine sticks 9 and 8 for a cost of 9 + 8 = 17. Now you have sticks = [17].
There is only one stick left, so you are done. The total cost is 4 + 9 + 17 = 30.Example 3:
Input: sticks = [5]
Output: 0
Explanation: There is only one stick, so you don't need to do anything. The total cost is 0.class Solution {
public int connectSticks(int[] sticks) {
if(sticks.length<=1) return 0;
PriorityQueue<Integer> heap = new PriorityQueue<>();
for(int i=0; i<sticks.length; i++){
heap.add(sticks[i]);
}
int cost = 0;
while(heap.size()>=2){
int first = heap.poll();
int second = heap.poll();
int sum = first+second;
cost += sum;
heap.add(sum);
}
return cost;
}
}
423. Reconstruct Original Digits from English
Given a string s containing an out-of-order English representation of digits 0-9, return the digits in ascending order.
Example 1:
Input: s = "owoztneoer"
Output: "012"Example 2:
Input: s = "fviefuro"
Output: "45"
class Solution {
public String originalDigits(String s) {
// building hashmap letter -> its frequency
char[] count = new char[26 + (int)'a'];
for(char letter: s.toCharArray()) {
count[letter]++;
}
// building hashmap digit -> its frequency
int[] out = new int[10];
// letter "z" is present only in "zero"
out[0] = count['z'];
// letter "w" is present only in "two"
out[2] = count['w'];
// letter "u" is present only in "four"
out[4] = count['u'];
// letter "x" is present only in "six"
out[6] = count['x'];
// letter "g" is present only in "eight"
out[8] = count['g'];
// letter "h" is present only in "three" and "eight"
out[3] = count['h'] - out[8];
// letter "f" is present only in "five" and "four"
out[5] = count['f'] - out[4];
// letter "s" is present only in "seven" and "six"
out[7] = count['s'] - out[6];
// letter "i" is present in "nine", "five", "six", and "eight"
out[9] = count['i'] - out[5] - out[6] - out[8];
// letter "n" is present in "one", "nine", and "seven"
out[1] = count['n'] - out[7] - 2 * out[9];
// building output string
StringBuilder output = new StringBuilder();
for(int i = 0; i < 10; i++)
for (int j = 0; j < out[i]; j++)
output.append(i);
return output.toString();
}
}1441. Build an Array With Stack Operations
You are given an integer array target and an integer n.
You have an empty stack with the two following operations:
"Push": pushes an integer to the top of the stack."Pop": removes the integer on the top of the stack.
You also have a stream of the integers in the range [1, n].
Use the two stack operations to make the numbers in the stack (from the bottom to the top) equal to target. You should follow the following rules:
- If the stream of the integers is not empty, pick the next integer from the stream and push it to the top of the stack.
- If the stack is not empty, pop the integer at the top of the stack.
- If, at any moment, the elements in the stack (from the bottom to the top) are equal to
target, do not read new integers from the stream and do not do more operations on the stack.
Return the stack operations needed to build target following the mentioned rules. If there are multiple valid answers, return any of them.
Example 1:
Input: target = [1,3], n = 3
Output: ["Push","Push","Pop","Push"]
Explanation: Initially the stack s is empty. The last element is the top of the stack.
Read 1 from the stream and push it to the stack. s = [1].
Read 2 from the stream and push it to the stack. s = [1,2].
Pop the integer on the top of the stack. s = [1].
Read 3 from the stream and push it to the stack. s = [1,3].Example 2:
Input: target = [1,2,3], n = 3
Output: ["Push","Push","Push"]
Explanation: Initially the stack s is empty. The last element is the top of the stack.
Read 1 from the stream and push it to the stack. s = [1].
Read 2 from the stream and push it to the stack. s = [1,2].
Read 3 from the stream and push it to the stack. s = [1,2,3].Example 3:
Input: target = [1,2], n = 4
Output: ["Push","Push"]
Explanation: Initially the stack s is empty. The last element is the top of the stack.
Read 1 from the stream and push it to the stack. s = [1].
Read 2 from the stream and push it to the stack. s = [1,2].
Since the stack (from the bottom to the top) is equal to target, we stop the stack operations.
The answers that read integer 3 from the stream are not accepted.class Solution {
public List<String> buildArray(int[] target, int n) {
int index = 0;
List<String> result = new LinkedList<>();
for(int i=1; i<=n; i++){
if(index < target.length && target[index]>i){
result.add("Push");
result.add("Pop");
}else if(index < target.length) {
result.add("Push");
index++;
}
}
return result;
}
}1146. Snapshot Array
Implement a SnapshotArray that supports the following interface:
SnapshotArray(int length)initializes an array-like data structure with the given length. Initially, each element equals 0.void set(index, val)sets the element at the givenindexto be equal toval.int snap()takes a snapshot of the array and returns thesnap_id: the total number of times we calledsnap()minus1.int get(index, snap_id)returns the value at the givenindex, at the time we took the snapshot with the givensnap_id
Example 1:
Input: ["SnapshotArray","set","snap","set","get"]
[[3],[0,5],[],[0,6],[0,0]]
Output: [null,null,0,null,5]
Explanation:
SnapshotArray snapshotArr = new SnapshotArray(3); // set the length to be 3
snapshotArr.set(0,5); // Set array[0] = 5
snapshotArr.snap(); // Take a snapshot, return snap_id = 0
snapshotArr.set(0,6);
snapshotArr.get(0,0); // Get the value of array[0] with snap_id = 0, return 5class SnapshotArray {
HashMap<Integer, HashMap<Integer, Integer>> map;
// index -> time -> value
int count;
public SnapshotArray(int length) {
count = 0;
map = new HashMap<>();
for (int i = 0; i < length; i++) {
map.put(i, new HashMap<>());
map.get(i).put(0, 0); // Initialize the initial snapshot (snap_id = 0) with 0 for each index
}
}
public void set(int index, int val) {
map.get(index).put(count, val);
}
public int snap() {
count++;
return count - 1;
}
public int get(int index, int snap_id) {
HashMap<Integer, Integer> snapshot = map.get(index);
while (snap_id > 0 && !snapshot.containsKey(snap_id)) {
snap_id--; // Find the closest previous snapshot that contains the value for the given index
}
System.out.println(snap_id);
System.out.println(snapshot);
return snapshot.getOrDefault(snap_id, 0);
}
}‘
Time limit exceeded
class SnapshotArray {
TreeMap<Integer, Integer[]> map;
int count;
int len;
public SnapshotArray(int length) {
count = 0;
map = new TreeMap<>();
this.len = length;
}
public void set(int index, int val) {
if(!map.containsKey(count)){
Integer[] temp = new Integer[this.len];
Arrays.fill(temp, 0);
map.put(count, temp);
}
Integer[] arr = map.get(count);
arr[index]=val;
}
public int snap() {
Integer[] curr = map.getOrDefault(count, new Integer[this.len]);
Integer[] temp = new Integer[this.len];
for(int i=0; i<temp.length; i++){
temp[i] = curr[i]!=null? curr[i]:0;
}
count++;
map.put(count, temp);
return count-1;
}
public int get(int index, int snap_id) {
while(snap_id>0 && !map.containsKey(snap_id)){
snap_id--;
}
if(!map.containsKey(snap_id)) return 0;
return map.get(snap_id)[index];
}
}
/**
* Your SnapshotArray object will be instantiated and called as such:
* SnapshotArray obj = new SnapshotArray(length);
* obj.set(index,val);
* int param_2 = obj.snap();
* int param_3 = obj.get(index,snap_id);
*/722. Remove Comments
Given a C++ program, remove comments from it. The program source is an array of strings source where source[i] is the ith line of the source code. This represents the result of splitting the original source code string by the newline character '\n'.
In C++, there are two types of comments, line comments, and block comments.
- The string
"//"denotes a line comment, which represents that it and the rest of the characters to the right of it in the same line should be ignored. - The string
"/*"denotes a block comment, which represents that all characters until the next (non-overlapping) occurrence of"*/"should be ignored. (Here, occurrences happen in reading order: line by line from left to right.) To be clear, the string"/*/"does not yet end the block comment, as the ending would be overlapping the beginning.
The first effective comment takes precedence over others.
- For example, if the string
"//"occurs in a block comment, it is ignored. - Similarly, if the string
"/*"occurs in a line or block comment, it is also ignored.
If a certain line of code is empty after removing comments, you must not output that line: each string in the answer list will be non-empty.
There will be no control characters, single quote, or double quote characters.
- For example,
source = "string s = "/* Not a comment. */";"will not be a test case.
Also, nothing else such as defines or macros will interfere with the comments.
It is guaranteed that every open block comment will eventually be closed, so "/*" outside of a line or block comment always starts a new comment.
Finally, implicit newline characters can be deleted by block comments. Please see the examples below for details.
After removing the comments from the source code, return the source code in the same format.
Example 1:
Input: source = ["/*Test program */", "int main()", "{ ", " // variable declaration ", "int a, b, c;", "/* This is a test", " multiline ", " comment for ", " testing */", "a = b + c;", "}"]
Output: ["int main()","{ "," ","int a, b, c;","a = b + c;","}"]
Explanation: The line by line code is visualized as below:
/*Test program */
int main()
{
// variable declaration
int a, b, c;
/* This is a test
multiline
comment for
testing */
a = b + c;
}
The string /* denotes a block comment, including line 1 and lines 6-9. The string // denotes line 4 as comments.
The line by line output code is visualized as below:
int main()
{
int a, b, c;
a = b + c;
}Example 2:
Input: source = ["a/*comment", "line", "more_comment*/b"]
Output: ["ab"]
Explanation: The original source string is "a/*comment\nline\nmore_comment*/b", where we have bolded the newline characters. After deletion, the implicit newline characters are deleted, leaving the string "ab", which when delimited by newline characters becomes ["ab"].class Solution {
public List<String> removeComments(String[] source) {
ArrayList<String> result = new ArrayList<>();
boolean block = false;
String temp = "";
for (String line : source) {
if (!block) {
temp = "";
}
for (int i = 0; i < line.length(); i++) {
if (block) {
if (line.charAt(i) == '*' && i + 1 < line.length() && line.charAt(i + 1) == '/') {
//when we are inside line comment and finding its endpoint.
block = false;
i++;
}
} else {
if (line.charAt(i) == '/' && i + 1 < line.length() && line.charAt(i + 1) == '/') {
// encountered the block comment so just directly break out of this current line and
// check for next line.
break;
}
if (line.charAt(i) == '/' && i + 1 < line.length() && line.charAt(i + 1) == '*') {
/* encountered the line comment and now jump to 1st if condition
for finding the closing side of line comment*/
block = true;
i++;
continue;
}
// if didnt encountered any comments just add answer in temp
temp += line.charAt(i);
}
}
if (!block) {
// add stored temp answer in result.
if (temp.length() > 0) {
result.add(temp);
}
}
}
return result;
}
}-> Copied from solution
412. Fizz Buzz
Given an integer n, return a string array answer (1-indexed) where:
answer[i] == "FizzBuzz"ifiis divisible by3and5.answer[i] == "Fizz"ifiis divisible by3.answer[i] == "Buzz"ifiis divisible by5.answer[i] == i(as a string) if none of the above conditions are true.
Example 1:
Input: n = 3
Output: ["1","2","Fizz"]Example 2:
Input: n = 5
Output: ["1","2","Fizz","4","Buzz"]Example 3:
Input: n = 15
Output: ["1","2","Fizz","4","Buzz","Fizz","7","8","Fizz","Buzz","11","Fizz","13","14","FizzBuzz"]class Solution {
public List<String> fizzBuzz(int n) {
List<String> res = new LinkedList<>();
for(int i=1; i<=n; i++){
if(i%3==0 && i%5==0){
res.add("FizzBuzz");
} else if (i%3==0){
res.add("Fizz");
} else if (i%5==0){
res.add("Buzz");
} else {
res.add(String.valueOf(i));
}
}
return res;
}
}Follow up, what if you cannot use % or /? What if 3 and 5 are not fixed?
class Solution { // d1=3, d2=5
public void fizzBuzz(int n, int d1, int d2) {
int d1Copy = d1;
int d2Copy = d2;
for(int i=1; i<=n; i++){
if(i==d1Copy && i==d2Copy){
System.out.println("FizzBuzz");
d1Copy += d1;
d2Copy += d2;
} else if (i==d1Copy){
System.out.println("Fizz");
d1Copy += d1;
} else if (i==d2Copy){
System.out.println("Buzz");
d2Copy += d2;
} else {
System.out.println(String.valueOf(i));
}
}
return res;
}
}Robot moving and delivering stuff
You will need to deliver parcels to different houses. You are given a set of directions in the form of a string. For eg, “^” means up, “v” means down, “<” means left and “>” means right. Return the number of houses visited.
public int getNumOfHousesVisited(String input){
Coord curr = new Coord(0, 0);
HashSet<Coord> visited = new HashSet<>();
visited.add(curr);
for(int i=0; i<input.length(); i++){
Coord next;
if(input.charAt(i) == '^'){
next = new Coord(curr.X-1, curr.y);
} else if (input.charAt(i) == 'v'){
next = new Coord(curr.X+1, curr.y);
} else if (input.charAt(i) == '>'){
next = new Coord(curr.X, curr.y+1);
} else {
next = new Coord(curr.X, curr.y-1);
}
visited.add(next);
curr = next;
}
return visited.size();
}
// If you have >1 robots delivering stuff.
// if input is "^v", then it means ^ is for the first robot
// and v is for the second robot.
public int getNumOfHousesVisited(String input, int N){
Queue<Coord> queue = new LinkedList<>();
for(int i=0; i<N; i++){
queue.add(new Coord(0, 0));
}
HashSet<Coord> visited = new HashSet<>();
visited.add(curr);
for(int i=0; i<input.length(); i++){
Coord next;
Coord curr = queue.poll();
if(input.charAt(i) == '^'){
next = new Coord(curr.X-1, curr.y);
} else if (input.charAt(i) == 'v'){
next = new Coord(curr.X+1, curr.y);
} else if (input.charAt(i) == '>'){
next = new Coord(curr.X, curr.y+1);
} else {
next = new Coord(curr.X, curr.y-1);
}
visited.add(next);
queue.push(next);
}
return visited.size();
}
public class Coord{
int x;
int y;
public Coord(int x, int y){
this.x = x;
this.y = y;
}
}1366. Rank Teams by Votes
In a special ranking system, each voter gives a rank from highest to lowest to all teams participating in the competition.
The ordering of teams is decided by who received the most position-one votes. If two or more teams tie in the first position, we consider the second position to resolve the conflict, if they tie again, we continue this process until the ties are resolved. If two or more teams are still tied after considering all positions, we rank them alphabetically based on their team letter.
You are given an array of strings votes which is the votes of all voters in the ranking systems. Sort all teams according to the ranking system described above.
Return a string of all teams sorted by the ranking system.
Example 1:
Input: votes = ["ABC","ACB","ABC","ACB","ACB"]
Output: "ACB"
Explanation:
Team A was ranked first place by 5 voters. No other team was voted as first place, so team A is the first team.
Team B was ranked second by 2 voters and ranked third by 3 voters.
Team C was ranked second by 3 voters and ranked third by 2 voters.
As most of the voters ranked C second, team C is the second team, and team B is the third.Example 2:
Input: votes = ["WXYZ","XYZW"]
Output: "XWYZ"
Explanation:
X is the winner due to the tie-breaking rule. X has the same votes as W for the first position, but X has one vote in the second position, while W does not have any votes in the second position.Example 3:
Input: votes = ["ZMNAGUEDSJYLBOPHRQICWFXTVK"]
Output: "ZMNAGUEDSJYLBOPHRQICWFXTVK"
Explanation: Only one voter, so their votes are used for the ranking.Constraints:
1 <= votes.length <= 10001 <= votes[i].length <= 26votes[i].length == votes[j].lengthfor0 <= i, j < votes.length.votes[i][j]is an English uppercase letter.- All characters of
votes[i]are unique. - All the characters that occur in
votes[0]also occur invotes[j]where1 <= j < votes.length.
import java.util.*;
class Solution {
public String rankTeams(String[] votes) {
int numTeams = votes[0].length();
Map<Character, int[]> voteCounts = new HashMap<>();
for (String vote : votes) {
for (int i = 0; i < numTeams; i++) {
char team = vote.charAt(i);
voteCounts.putIfAbsent(team, new int[numTeams]);
voteCounts.get(team)[i]++;
}
}
TreeMap<Character, int[]> treeMap = new TreeMap<>((k1, k2) -> {
for (int i = 0; i < numTeams; i++) {
int compare = voteCounts.get(k2)[i] - voteCounts.get(k1)[i];
if (compare != 0) {
return compare;
}
}
return k1 - k2; // If all positions have the same vote count, sort alphabetically
});
treeMap.putAll(voteCounts);
StringBuilder result = new StringBuilder();
for (char team : treeMap.keySet()) {
result.append(team);
}
return result.toString();
}
}My initial approach was to use a summation. Eg, if a team was voted at position i, i would add i to the hashmap assigned to that team.
From ChatGPT:
In your original code, you were summing the positions of the characters as vote counts. However, the given ranking system states that the ordering is determined by the number of position-one votes each team receives. In your logic, you were simply adding the positions of each team character in the votes. This approach doesn’t reflect the number of times each team received a vote in the first position.
439. Ternary Expression Parser
Given a string expression representing arbitrarily nested ternary expressions, evaluate the expression, and return the result of it.
You can always assume that the given expression is valid and only contains digits, '?', ':', 'T', and 'F' where 'T' is true and 'F' is false. All the numbers in the expression are one-digit numbers (i.e., in the range [0, 9]).
The conditional expressions group right-to-left (as usual in most languages), and the result of the expression will always evaluate to either a digit, 'T' or 'F'.
Example 1:
Input: expression = "T?2:3"
Output: "2"
Explanation: If true, then result is 2; otherwise result is 3.Example 2:
Input: expression = "F?1:T?4:5"
Output: "4"
Explanation: The conditional expressions group right-to-left. Using parenthesis, it is read/evaluated as:
"(F ? 1 : (T ? 4 : 5))" --> "(F ? 1 : 4)" --> "4"
or "(F ? 1 : (T ? 4 : 5))" --> "(T ? 4 : 5)" --> "4"Example 3:
Input: expression = "T?T?F:5:3"
Output: "F"
Explanation: The conditional expressions group right-to-left. Using parenthesis, it is read/evaluated as:
"(T ? (T ? F : 5) : 3)" --> "(T ? F : 3)" --> "F"
"(T ? (T ? F : 5) : 3)" --> "(T ? F : 5)" --> "F"Constraints:
5 <= expression.length <= 104expressionconsists of digits,'T','F','?', and':'.- It is guaranteed that
expressionis a valid ternary expression and that each number is a one-digit number.
class Solution {
public String parseTernary(String expression) {
Stack<Character> stack = new Stack();
int i=expression.length()-1;
while(i>=0){
Character current = expression.charAt(i);
if(current == '?'){
Character onTrue = stack.pop();
Character onFalse = stack.pop();
Character leftChar = expression.charAt(i-1);
stack.push(leftChar == 'T' ? onTrue: onFalse);
i--;
} else if (current != ':'){
stack.push(current);
}
i--;
}
return String.valueOf(stack.peek());
}
}