By Long Luo

This article is the solution 4 Approaches: Stack, Array, Greedy and O(n) Time O(1) Space of Problem 946. Validate Stack Sequences.

Intuition

All elements must be pushed in in order. The key is how to pop them out?

Assuming that the value of the current top element of the stack is \(1\), and the next value to be popped in the corresponding popped sequence is also \(1\), then this value must be popped out immediately. Because the subsequent push will change the top element of the stack to a value other than \(2\), so the popped sequence of the popped numbers does not correspond.

Pushes each number in the pushed queue onto the stack, checking to see if the number is the next value to be popped in the popped sequence, and pops it if so.

Finally, check that not all the popped values are popped.

Stack

We can use a Stack to simulate the process.

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

public boolean validateStackSequences(int[] pushed, int[] popped) {
    if (popped == null || pushed.length <= 1) {
        return true;
    }

    int len = pushed.length;
    int popIdx = 0;
    Stack<Integer> stack = new Stack<>();
    for (int i = 0; i < len; i++) {
        stack.push(pushed[i]);
        while (!stack.empty() && popIdx < len && stack.peek() == popped[popIdx]) {
            stack.pop();
            popIdx++;
        }
    }

    return popIdx == len;
}

Analysis

• Time Complexity: \(O(N)\)
• Space Complexity: \(O(N)\)

By Long Luo

This article is the solution Stack Solution with Easy Detailed Explanation of Problem 1249. Minimum Remove to Make Valid Parentheses.

Intuition

First we can use Brute Force to into a two-step` algorithm:

1. find all the \((\) and \()\) and get their indices;
2. determine the indices that need to be deleted;
3. creates a new string from the index of the deleted characters.

We can use a Stack to record the indices of all \((\) and \()\) s. When scanning to the end of the string, all indices remaining in the Stack are \((\) and \()\) s that do not match.

We also need to use a \(\texttt{Set}\) to keep track of unmatched \((\) and \()\) s. Then Delete each character that needs to be deleted according to the indices, and return the recreated string.

The code is as follows:

By Long Luo

This article is the solution Stack Solution with Easy Detailed Explanation of Problem 71. Simplify Path .

Intuition

We can just simulate the process from the begin to end.

First we split the given string \(\textit{path}\) into a list of strings by the slash \(/\), denoted as names. According to the canonical path in the problem description, the strings contained in names can only be the following:

1. empty string;
2. a dot .;
3. two dots ..;
4. a directory name containing only English letters, numbers, or _.

If we meet empty string or ., we can ignore them because empty string means nothing, and . means the current directory itself, so we don’t need to change directories.

If we meet .. or “directory names”, we can use a Stack to maintain each directory name in the path. When we encounter “two dots”, we need to change the directory to the parent directory. As the stack is not empty, we pop the directory of the stack. When we encounter a “directory”, we put it to the stack.

Finally we need to iterate each string in names and do the above. After all operations are completed, we connect the strings from the bottom of the stack to the top of the stack with /, and then add / at the top to indicate the root directory, and we can get the simplified Canonical path.

By Long Luo

This article is the solution Easy Backtracking Approach: Deduplicating and Pruning of Problem 39. Combination Sum.

Backtracking

It’s a typical Backtracking algorithm.

We can easily draw the tree below.

Take \(\textit{target} = 7\) as the root node and subtract the value of the edge while creating a child node.

Stop it when the value of the node is \(0\) or a negative number.

All paths from the root node to leaf node \(0\) are the results of the question.

Let’s coding.

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

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        if (candidates == null || target == 0) {
            return ans;
        }

        backtrack(ans, new ArrayList<>(), candidates, target);
        return ans;
    }

    public static void backtrack(List<List<Integer>> res, List<Integer> list, int[] candidates, int remain) {
        if (remain < 0) {
            return;
        }

        if (remain == 0) {
            res.add(new ArrayList<>(list));
            return;
        }

        int len = candidates.length;
        for (int i = 0; i < len; i++) {
            int num = candidates[i];
            list.add(num);
            backtrack(res, list, candidates, remain - num);
            list.remove(list.size() - 1);
        }
    }
}

Take \(\textit{target} = 7\) for example, \([[2, 2, 3], [2, 3, 2], [3, 2, 2], [7]]\) are the answer.

However, the correct answer is \([[7], [2, 2, 3]]\).

Since it requires that each solution is not in order, so the \([2, 2, 3]\) and \([2, 3, 2]\) are the same answer.

What’s problem?

When and how did we duplicate the path?

Why Duplicated?

At each node of the tree, all the candidates were searched and used, so there is a duplicate list.

Is it possible to deduplicate while searching?

Of course we can.

We have to search the elements in order while searching, since the output is not by order. We search from the certain position in the next round.

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

public static void backtrack(List<List<Integer>> res, List<Integer> list, int[] candidates, int start, int remain) {
    if (remain < 0) {
        return;
    }

    if (remain == 0) {
        res.add(new ArrayList<>(list));
        return;
    }

    int len = candidates.length;
    for (int i = start; i < len; i++) {
        int num = candidates[i];
        list.add(num);
        backtrack(res, list, candidates, i, remain - num);
        list.remove(list.size() - 1);
    }
}

By now we deduplicating it and complete the problem.

By Long Luo

This article is the solution 9 Approaches：Brute Force, Count, Hash, In-place Marked, Sorting, Index Sort, Binary Search, Bit Manipulation, Fast Slow Pointers of Problem 287. Find the Duplicate Number.

Here are 9 approaches to solve this problem in Java, which is Brute Force, Count, Hash, In-place Marked, Sorting, Index Sort, Binary Search, Bit Manipulation, Fast Slow Pointers.

Inspired by @user2670f and his solution [C++] 7 Different solutions to this problem (with relaxed constraints) , I added 3 more approaches.

Brute Force (2 Loops)

Since solve the problem without modifying the array nums and uses only constant extra space, we can use Brute Force to solve it.

It’s easy to use 2 loops to do it, but the time complexity is \(O(n^2)\), so it wouldn’t accepted as timeout.

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

// 2 Loops
public static int findDuplicate_2loops(int[] nums) {
    int len = nums.length;
    for (int i = 0; i < len; i++) {
        for (int j = i + 1; j < len; j++) {
            if (nums[i] == nums[j]) {
                return nums[i];
            }
        }
    }

    return len;
}

Analysis

• Time Complexity: \(O(n^2)\)
• Space Complexity: \(O(1)\)

Count

Count the frequency of the num in the array.

With extra \(O(n)\) space, without modifying the input.

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

public static int findDuplicate(int[] nums) {
    int len = nums.length;
    int[] cnt = new int[len + 1];
    for (int i = 0; i < len; i++) {
        cnt[nums[i]]++;
        if (cnt[nums[i]] > 1) {
            return nums[i];
        }
    }

    return len;
}

Analysis

• Time Complexity: \(O(n)\)
• Space Complexity: \(O(n)\)

Hash

Using a \(\texttt{HashSet}\) to record the occurrence of each number.

With extra \(O(n)\) space, without modifying the input.

1
2
3
4
5
6
7
8
9
10
11

public static int findDuplicate_set(int[] nums) {
    Set<Integer> set = new HashSet<>();
    int len = nums.length;
    for (int i = 0; i < len; i++) {
        if (!set.add(nums[i])) {
            return nums[i];
        }
    }

    return len;
}

Analysis

• Time Complexity: \(O(n)\)
• Space Complexity: \(O(n)\)

Marking visited value within the array

Since all values of the array are between \([1 \dots n]\) and the array size is \(n+1\), while scanning the array from left to right, we set the \(\textit{nums}[n]\) to its negative value.

With extra \(O(1)\) space, with modifying the input.

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

// Visited
public static int findDuplicate_mark(int[] nums) {
    int len = nums.length;
    for (int num : nums) {
        int idx = Math.abs(num);
        if (nums[idx] < 0) {
            return idx;
        }
        nums[idx] = -nums[idx];
    }

    return len;
}

Analysis

• Time Complexity: \(O(n)\)
• Space Complexity: \(O(1)\)

Sort

Sorting the array first, then use a loop from \(1\) to \(n\).

With extra \(O(nlogn)\) space, modifying the input.

1
2
3
4
5
6
7
8
9
10
11

public static int findDuplicate_sort(int[] nums) {
    Arrays.sort(nums);
    int len = nums.length;
    for (int i = 1; i < len; i++) {
        if (nums[i] == nums[i - 1]) {
            return nums[i];
        }
    }

    return len;
}

Analysis

• Time Complexity: \(O(nlogn)\)
• Space Complexity: \(O(logn)\)