MrainW's Home

All things come to those who wait!

0%

Posted on In ,
Symbols count in article: 1k Reading time ≈ 1 mins.

Question

The next greater element of some element x in an array is the first greater element that is to the right of x in the same array.

You are given two distinct 0-indexed integer arrays nums1 and nums2, where nums1 is a subset of nums2.

For each 0 <= i < nums1.length, find the index j such that nums1[i] == nums2[j] and determine the next greater element of nums2[j] in nums2. If there is no next greater element, then the answer for this query is -1.

Return an array ans of length nums1.length such that ans[i] is the next greater element as described above.

https://leetcode.com/problems/next-greater-element-i/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map = new HashMap<>();
        Stack<Integer> stack = new Stack<>();
        for (int i = nums2.length -1; i >= 0; i--){
            while (!stack.isEmpty() && nums2[i] >= stack.peek()) stack.pop();
            map.put(nums2[i], stack.isEmpty() ? -1 : stack.peek());
            stack.push(nums2[i]);
        }
        int[] res = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) res[i] = map.get(nums1[i]);
        return res;
    }
}

Time complexity: O(n)

Space complexity: O(n)

Posted on In ,
Symbols count in article: 774 Reading time ≈ 1 mins.

Question

Given a circular integer array nums (i.e., the next element of nums[nums.length - 1] is nums[0]), return the next greater number for every element in nums.

The next greater number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn’t exist, return -1 for this number.

https://leetcode.com/problems/next-greater-element-ii/

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length, res[] = new int[n];
        Stack<Integer> stack = new Stack<>();
        for (int i = 2 * n - 1; i >= 0; i--){
            while (!stack.isEmpty() && nums[i % n] >= stack.peek()) stack.pop();
            res[i % n] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(nums[i % n]);
        }
        return res;
    }
}

Time complexity: O(n)

Space complexity: O(n)

Posted on In ,
Symbols count in article: 1.1k Reading time ≈ 1 mins.

Question

Design a stack which supports the following operations.

Implement the CustomStack class:

  • CustomStack(int maxSize) Initializes the object with maxSize which is the maximum number of elements in the stack or do nothing if the stack reached the maxSize.
  • void push(int x) Adds x to the top of the stack if the stack hasn’t reached the maxSize.
  • int pop() Pops and returns the top of stack or -1 if the stack is empty.
  • void inc(int k, int val) Increments the bottom k elements of the stack by val. If there are less than k elements in the stack, just increment all the elements in the stack.

https://leetcode.com/problems/design-a-stack-with-increment-operation/

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
class CustomStack {
    int n;
    int[] inc;
    Stack<Integer> stack = new Stack<>();
    public CustomStack(int maxSize) {
        n = maxSize;
        inc = new int[n];
    }
    
    public void push(int x) {
        if(stack.size()<n) stack.push(x);
    }
    
    public int pop() {
        int i = stack.size()-1;
        if(i<0) return -1;
        if(i>0) inc[i-1] += inc[i];
        int res = stack.pop() + inc[i];
        inc[i] = 0;
        return res;
    }
    
    public void increment(int k, int val) {
        int i = Math.min(k, stack.size()) - 1;
        if(i >= 0) inc[i] += val;
    }
}

Posted on In ,
Symbols count in article: 2k Reading time ≈ 2 mins.

Question

Design your implementation of the circular double-ended queue (deque).

Implement the MyCircularDeque class:

  • MyCircularDeque(int k) Initializes the deque with a maximum size of k.
  • boolean insertFront() Adds an item at the front of Deque. Returns true if the operation is successful, or false otherwise.
  • boolean insertLast() Adds an item at the rear of Deque. Returns true if the operation is successful, or false otherwise.
  • boolean deleteFront() Deletes an item from the front of Deque. Returns true if the operation is successful, or false otherwise.
  • boolean deleteLast() Deletes an item from the rear of Deque. Returns true if the operation is successful, or false otherwise.
  • int getFront() Returns the front item from the Deque. Returns -1 if the deque is empty.
  • int getRear() Returns the last item from Deque. Returns -1 if the deque is empty.
  • boolean isEmpty() Returns true if the deque is empty, or false otherwise.
  • boolean isFull() Returns true if the deque is full, or false otherwise.

https://leetcode.com/problems/design-circular-deque/

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
class MyCircularDeque {
    int[] q;
    int front = 0, rear = -1, size = 0, capacity;
    public MyCircularDeque(int k) {
        q = new int[k];
        capacity = k;
    }
    
    public boolean insertFront(int value) {
        if(isFull()) return false;
        if(--front < 0) front +=capacity;
        q[front] = value;
        size++;
        if(size == 1) rear = front;
        return true;
    }
    
    public boolean insertLast(int value) {
        if (isFull()) return false;
        rear = (rear + 1) % capacity;
        q[rear] = value;
        size++;
        return true; 
    }
    
    public boolean deleteFront() {
        if (isEmpty()) return false;
        front = (front + 1) % capacity;
        size--;
        return true;
    }
    
    public boolean deleteLast() {
        if(isEmpty()) return false;
        if(--rear < 0) rear += capacity;
        size--;
        return true;
    }
    
    public int getFront() {
        return isEmpty() ? -1 : q[front];
    }
    
    public int getRear() {
        return isEmpty() ? -1 : q[rear];
    }
    
    public boolean isEmpty() {
        return size == 0;
    }
    
    public boolean isFull() {
        return size == capacity;
    }
}

Time Complexity:

MyCircularDeque, O(1). insertFront, O(1). insertLast, O(1). deleteFront, O(1). deleteLast, O(1). getFront, O(1). getRear, O(1). isEmpty(): O(1), isFull(): O(1).

Space: O(k).

Posted on In ,
Symbols count in article: 923 Reading time ≈ 1 mins.

Question

  • Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).

    Implement the MyQueue class:

    • void push(int x) Pushes element x to the back of the queue.
    • int pop() Removes the element from the front of the queue and returns it.
    • int peek() Returns the element at the front of the queue.
    • boolean empty() Returns true if the queue is empty, false otherwise.

https://leetcode.com/problems/implement-queue-using-stacks/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class MyQueue {

    Stack<Integer> queue = new Stack<>();
    Stack<Integer> stack = new Stack<>();
    public void push(int x){
        stack.push(x);
    }
    public int pop(){
        peek();
        return queue.pop();
    }
    public int peek(){
        if(queue.empty())
            while(!stack.empty())
                queue.push(stack.pop());
        return queue.peek();
    }
    public boolean empty(){
        return stack.empty() && queue.empty();
    }
}

Complexity:

Time complexity: O(1)

Space complexity: O(n)

Posted on In ,
Symbols count in article: 1.2k Reading time ≈ 1 mins.

Question

  • Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).

    Implement the MyStack class:

    • void push(int x) Pushes element x to the top of the stack.
    • int pop() Removes the element on the top of the stack and returns it.
    • int top() Returns the element on the top of the stack.
    • boolean empty() Returns true if the stack is empty, false otherwise.

https://leetcode.com/problems/implement-stack-using-queues/

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 MyStack {
    //push O(n)
    public MyStack() {
    }
    Queue<Integer> q1 = new LinkedList<>();
    Queue<Integer> q2 = new LinkedList<>();
    public void push(int x){
        if(q1.isEmpty()) q1.offer(x);
        while(!q2.isEmpty()) q1.offer(q2.poll());
        while(!q1.isEmpty()) q2.offer(q1.poll());
    }
    public int pop(){return q2.poll();}
    public int top(){return q2.peek();}
    public boolean empty(){return q1.isEmpty() && q2.isEmpty();}
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

Complexity:

Time complexity:

push: O(n)

pop/top/empty: O(1)

Space complexity: O(n)

Posted on In ,
Symbols count in article: 1.2k Reading time ≈ 1 mins.

Question

Design your implementation of the circular queue. The circular queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle. It is also called “Ring Buffer”.

One of the benefits of the circular queue is that we can make use of the spaces in front of the queue. In a normal queue, once the queue becomes full, we cannot insert the next element even if there is a space in front of the queue. But using the circular queue, we can use the space to store new values.

https://leetcode.com/problems/design-circular-queue/

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
class MyCircularQueue {
    int[] q;
    int front, rear, size;
    public MyCircularQueue(int k) {
        front = 0;
        rear = -1;
        q = new int[k];
    }
    
    public boolean enQueue(int value) {
        if(!isFull()){
            rear=(rear + 1) % q.length;
            q[rear] = value;
            size++;
            return true;
        } else return false;
    }
    
    public boolean deQueue() {
        if(!isEmpty()){
            front = (front + 1) % q.length;
            size--;
            return true;
        } else return false;
    }
    
    public int Front() {
        return isEmpty() ? -1 : q[front];
    }
    
    public int Rear() {
        return isEmpty() ? -1 : q[rear];
    }
    
    public boolean isEmpty() {
        return size == 0;
    }
    
    public boolean isFull() {
        return size == q.length;
    }
}

Complexity: O(1)

Space complexity: O(k)

Posted on In ,
Symbols count in article: 851 Reading time ≈ 1 mins.

Question

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

  • MinStack() initializes the stack object.
  • void push(int val) pushes the element val onto the stack.
  • void pop() removes the element on the top of the stack.
  • int top() gets the top element of the stack.
  • int getMin() retrieves the minimum element in the stack.

https://leetcode.com/problems/min-stack/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class MinStack {
    //two stack
    Stack<int[]> stack = new Stack<>();
    public void push(int x) {
        if(stack.isEmpty()){
            stack.push(new int[]{x,x});
            return;
        }
        int min = stack.peek()[1];
        stack.push(new int[]{x,Math.min(x,min)});
    }
    public void pop(){
        stack.pop();
    }
    
    public int top(){
        return stack.peek()[0];
    }
    
    public int getMin(){
        return stack.peek()[1];
    }
}

Complexity:

Time complexity: O(1)

Space complexity: O(1)

Posted on In ,
Symbols count in article: 919 Reading time ≈ 1 mins.

Question

Given a string s, sort it in decreasing order based on the frequency of the characters. The frequency of a character is the number of times it appears in the string.

Return the sorted string. If there are multiple answers, return any of them.

https://leetcode.com/problems/sort-characters-by-frequency/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public String frequencySort(String s) {
        Map<Character, Integer> map = new HashMap<>();
        for (char c : s.toCharArray())
            map.put(c, map.getOrDefault(c, 0) + 1);
        List<Character> [] bucket = new List[s.length() + 1];
        for (char key : map.keySet()){
            int frequency = map.get(key);
            if (bucket[frequency] == null) bucket[frequency] = new ArrayList<>();
            bucket[frequency].add(key);
        }
        StringBuilder sb = new StringBuilder();
        for (int pos = bucket.length - 1; pos > 0; pos--)
            if (bucket[pos] != null)
                for (char c : bucket[pos])
                    for (int i = 0; i < pos; i++)
                        sb.append(c);
        return sb.toString();
    }
}

Complexity:

Time complexity: O(n)

Space complexity: O(n)

Posted on In ,
Symbols count in article: 1k Reading time ≈ 1 mins.

Question

Given the head of a linked list, return the list after sorting it in ascending order.

https://leetcode.com/problems/sort-list/

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
class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null){
            return head;
        }
        ListNode mid = findMid(head);
        ListNode right = sortList(mid.next);
        mid.next = null;
        ListNode left = sortList(head);
        return merge(left, right);
    }
    private ListNode findMid(ListNode head){
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
    private ListNode merge(ListNode head1, ListNode head2){
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while (head1 != null && head2 != null){
            if (head1.val < head2.val){
                cur.next = head1;
                head1 = head1.next;
            } else{
                cur.next = head2;
                head2 = head2.next;
            }
            cur = cur.next;
        }
        if (head1 == null) cur.next = head2;
        else cur.next = head1;
        return dummy.next;
    }
}

Complexity:

Time complexity: O( nlogn)

Space complexity: O(logn)