LeetCode [714] Max Stack

 716. Max Stack

Easy

Design a max stack data structure that supports the stack operations and supports finding the stack's maximum element.

Implement the MaxStack class:

• MaxStack() Initializes the stack object.
• void push(int x) Pushes element x onto the stack.
• int pop() Removes the element on top of the stack and returns it.
• int top() Gets the element on the top of the stack without removing it.
• int peekMax() Retrieves the maximum element in the stack without removing it.
• int popMax() Retrieves the maximum element in the stack and removes it. If there is more than one maximum element, only remove the top-most one.

 

Example 1:

Input
["MaxStack", "push", "push", "push", "top", "popMax", "top", "peekMax", "pop", "top"]
[[], [5], [1], [5], [], [], [], [], [], []]
Output
[null, null, null, null, 5, 5, 1, 5, 1, 5]

Explanation
MaxStack stk = new MaxStack();
stk.push(5);   // [5] the top of the stack and the maximum number is 5.
stk.push(1);   // [5, 1] the top of the stack is 1, but the maximum is 5.
stk.push(5);   // [5, 1, 5] the top of the stack is 5, which is also the maximum, because it is the top most one.
stk.top();     // return 5, [5, 1, 5] the stack did not change.
stk.popMax();  // return 5, [5, 1] the stack is changed now, and the top is different from the max.
stk.top();     // return 1, [5, 1] the stack did not change.
stk.peekMax(); // return 5, [5, 1] the stack did not change.
stk.pop();     // return 1, [5] the top of the stack and the max element is now 5.
stk.top();     // return 5, [5] the stack did not change.

 

Constraints:

• -107 <= x <= 107
• At most 104 calls will be made to push, pop, top, peekMax, and popMax.
• There will be at least one element in the stack when pop, top, peekMax, or popMax is called.

 

Follow up: Could you come up with a solution that supports O(1) for each top call and O(logn) for each other call? 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58

class MaxStack { Stack<Integer> stk = new Stack<>(); Stack<Integer> stkM = new Stack<>(); /** initialize your data structure here. */ public MaxStack() { } public void push(int x) { stk.add(x); if(stkM.isEmpty()) stkM.add(x); else{ if(stkM.peek()<=x) stkM.add(x); } } public int pop() { int x = stk.pop(); if(x==stkM.peek()) stkM.pop(); return x; } public int top() { return stk.peek(); } public int peekMax() { return stkM.peek(); } public int popMax() { Stack<Integer> stkT = new Stack<>(); int max = stkM.peek(); while(stk.peek()!=max){ stkT.add(stk.pop()); } stk.pop(); stkM.pop(); while(!stkT.isEmpty()){ int t = stkT.pop(); stk.add(t); if(stkM.isEmpty() || t>=stkM.peek()) stkM.add(t); } return max; } } /** * Your MaxStack object will be instantiated and called as such: * MaxStack obj = new MaxStack(); * obj.push(x); * int param_2 = obj.pop(); * int param_3 = obj.top(); * int param_4 = obj.peekMax(); * int param_5 = obj.popMax(); */

LeetCode [540] Single Element in a Sorted Array

 540. Single Element in a Sorted Array

Medium

You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once. Find this single element that appears only once.

Follow up: Your solution should run in O(log n) time and O(1) space.

 

Example 1:

Input: nums = [1,1,2,3,3,4,4,8,8]
Output: 2

Example 2:

Input: nums = [3,3,7,7,10,11,11]
Output: 10

 

Constraints:

• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 10^5

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

class Solution { public int singleNonDuplicate(int[] nums) { int n = nums.length; int l = 0, r = n-1; while(l<=r){ int m = (l+r)/2; if((m==l || nums[m-1]!=nums[m]) && (m==r || nums[m]!=nums[m+1])){ return nums[m]; }else{ //the first element if(m==l || nums[m-1]!=nums[m]){ int leftLen = m+2; if(leftLen%2==0) l = leftLen; else r=m-1; }else{//the second element int leftLen = m+1; if(leftLen%2==0) l = leftLen; else r=m-1; } } } return -1; } }

LeetCode [945] Minimum Increment to Make Array Unique

 945. Minimum Increment to Make Array Unique

Medium

Given an array of integers A, a move consists of choosing any A[i], and incrementing it by 1.

Return the least number of moves to make every value in A unique.

 

Example 1:

Input: [1,2,2]
Output: 1
Explanation:  After 1 move, the array could be [1, 2, 3].

Example 2:

Input: [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.

 

Note:

1. 0 <= A.length <= 40000
2. 0 <= A[i] < 40000

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

class Solution { public int minIncrementForUnique(int[] A) { int n = A.length; Arrays.sort(A); int moves = 0; for(int i=1; i<n; ++i){ if(A[i]<=A[i-1]){ int v = A[i-1]+1; moves += v-A[i]; A[i] = v; } } return moves; } }

LeetCode [1151] Minimum Swaps to Group All 1's Together

 1151. Minimum Swaps to Group All 1's Together

Medium

Given a binary array data, return the minimum number of swaps required to group all 1’s present in the array together in any place in the array.

 

Example 1:

Input: data = [1,0,1,0,1]
Output: 1
Explanation: 
There are 3 ways to group all 1's together:
[1,1,1,0,0] using 1 swap.
[0,1,1,1,0] using 2 swaps.
[0,0,1,1,1] using 1 swap.
The minimum is 1.

Example 2:

Input: data = [0,0,0,1,0]
Output: 0
Explanation: 
Since there is only one 1 in the array, no swaps needed.

Example 3:

Input: data = [1,0,1,0,1,0,0,1,1,0,1]
Output: 3
Explanation: 
One possible solution that uses 3 swaps is [0,0,0,0,0,1,1,1,1,1,1].

Example 4:

Input: data = [1,0,1,0,1,0,1,1,1,0,1,0,0,1,1,1,0,0,1,1,1,0,1,0,1,1,0,0,0,1,1,1,1,0,0,1]
Output: 8

 

Constraints:

• 1 <= data.length <= 105
• data[i] is 0 or 1.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

class Solution { public int minSwaps(int[] data) { int n = data.length; int[] dp = new int[n]; int cnt1 = 0;//number of ones int minSwaps = Integer.MAX_VALUE; for(int i=0; i<n; ++i){ if(data[i]==1){ cnt1++; dp[i] = cnt1; } } if(cnt1==0) return 0; int l = 0; int left1 = 0; while(l + cnt1 - 1 < n){ int swaps = left1 + cnt1 - dp[l+cnt1-1]; minSwaps = Math.min(minSwaps, swaps); left1 +=data[l++]; } return minSwaps; } }

LeetCode [532] K-diff Pairs in an Array

 532. K-diff Pairs in an Array

Medium

Given an array of integers nums and an integer k, return the number of unique k-diff pairs in the array.

A k-diff pair is an integer pair (nums[i], nums[j]), where the following are true:

• 0 <= i, j < nums.length
• i != j
• |nums[i] - nums[j]| == k

Notice that |val| denotes the absolute value of val.

 

Example 1:

Input: nums = [3,1,4,1,5], k = 2
Output: 2
Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5).
Although we have two 1s in the input, we should only return the number of unique pairs.

Example 2:

Input: nums = [1,2,3,4,5], k = 1
Output: 4
Explanation: There are four 1-diff pairs in the array, (1, 2), (2, 3), (3, 4) and (4, 5).

Example 3:

Input: nums = [1,3,1,5,4], k = 0
Output: 1
Explanation: There is one 0-diff pair in the array, (1, 1).

Example 4:

Input: nums = [1,2,4,4,3,3,0,9,2,3], k = 3
Output: 2

Example 5:

Input: nums = [-1,-2,-3], k = 1
Output: 2

 

Constraints:

• 1 <= nums.length <= 104
• -107 <= nums[i] <= 107
• 0 <= k <= 107

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

class Solution { public int findPairs(int[] nums, int k) { Arrays.sort(nums); int n = nums.length; int cnt = 0; Set<Integer> set = new HashSet<>(); for(int i=0; i<n; ++i){ if(i>0 && nums[i]==nums[i-1]){ if(k>0) continue; if(k==0 && i>1 && nums[i-1]==nums[i-2]) continue; } int v = nums[i]; if(set.contains(v-k)) cnt += 1; set.add(v); } return cnt; } }

LeetCode [1297] Maximum Number of Occurrences of a Substring

 1297. Maximum Number of Occurrences of a Substring

Medium

Given a string s, return the maximum number of ocurrences of any substring under the following rules:

• The number of unique characters in the substring must be less than or equal to maxLetters.
• The substring size must be between minSize and maxSize inclusive.

 

Example 1:

Input: s = "aababcaab", maxLetters = 2, minSize = 3, maxSize = 4
Output: 2
Explanation: Substring "aab" has 2 ocurrences in the original string.
It satisfies the conditions, 2 unique letters and size 3 (between minSize and maxSize).

Example 2:

Input: s = "aaaa", maxLetters = 1, minSize = 3, maxSize = 3
Output: 2
Explanation: Substring "aaa" occur 2 times in the string. It can overlap.

Example 3:

Input: s = "aabcabcab", maxLetters = 2, minSize = 2, maxSize = 3
Output: 3

Example 4:

Input: s = "abcde", maxLetters = 2, minSize = 3, maxSize = 3
Output: 0

 

Constraints:

• 1 <= s.length <= 10^5
• 1 <= maxLetters <= 26
• 1 <= minSize <= maxSize <= min(26, s.length)
• s only contains lowercase English letters.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

class Solution { public int maxFreq(String s, int maxLetters, int minSize, int maxSize) { Map<String, Integer> cntW = new HashMap<>(); int[] cntL = new int[26]; int unqL = 0; int maxCnt = 0; int i = 0, j = 0, n = s.length(); while(j<n){ int c = s.charAt(j)-'a'; if(cntL[c]==0) unqL++; cntL[c]++; while(j-i+1>maxSize || unqL>maxLetters){ c = s.charAt(i)-'a'; cntL[c]--; if(cntL[c]==0) unqL--; i++; } while(j-i+1>=minSize){ String sub = s.substring(i, j+1); cntW.put(sub, cntW.getOrDefault(sub, 0)+1); // System.out.println(sub+" "+cntW.get(sub)); if(cntW.get(sub)>maxCnt) maxCnt = cntW.get(sub); c = s.charAt(i)-'a'; cntL[c]--; if(cntL[c]==0) unqL--; i++; } j++; } return maxCnt; } }