Problem Statement

In this problem, we are looking to determine whether a sequence is good, or not. First, let’s define some important terms for this problem.

“Good” Sequence: A sequence is defined as “good” if every possible connected subsequence within the original sequence contains at least one unique element, i.e. an element such that no other element of that subsequence has the same value. Connected Subsequence: A connected subsequence is defined as a subsequence consisting of consecutive elements.

The elements of the sequence are in the range of , and the length of the sequence is in the range of . Now, given a sequence of integers, decide whether or not it is “good” by returning true/false appropriately. Also, determine the runtime of your solution.

Here’s the method signature, in Java.

    //Returns true if seq is "good", else false.
    public boolean goodSequence(int[] seq){
        // Your code here

Test Cases

Test Case 1

Input: [1, 2, 3]
Output: true
[1], [2], [3], [1,2], [2,3], [1,2,3] are all "good"

Test Case 2

Input: [1, 2, 1]
Output: true
[1], [2], [1], [1,2], [2,1], [1,2,1] are all "good"

Test Case 3

Input: [1, 2, 1, 2]
Output: false
[1,2,1,2] has no unique element

Test Case 4

Input: [2, 2]
Output: false
[2,2] has no unique element

Test Case 5

Input: [1, 2, 1, 3, 2, 1, 4, 3, 2, 1]
Output: true
Hint: Try thinking about what happens to a certain subsequence as items are added or removed.

Click Below to see the Solution

Click Me

Part 1: Main Idea

The simplest approach to this problem is to consider every possible subsequence of the given seq array, look at the elements within this subsequence, and check if there is a unique element or not. If no unique element exists, we can short-circuit to return false. Otherwise, we must continue checking other subsequences.

This solution boils down to a runtime. If we consider every possible subsequence, this takes time. For each subsequence, checking whether or not a unique element exists takes time in the worst case, resulting in a total of .

Part 2: Improvements

Since we must take a look at each subsequence, there is no way to speed this part up. However, we can improve the checking of each subsequence. Instead of running through each subsequence and looking for the existence of a unique element, we can keep a HashMap at the start of each iteration through the first for loop, mapping {element -> count}. Then, this reduces the runtime for determining uniqueness of the subsequence to amortized constant time.

Part 3: Code it Up

Code for the above algorithm can be seen below:

    //Returns true if seq is "good", else false
    public boolean goodSequence(int[] seq) {
        for (int i = 0; i < seq.length() - 1; i++) {
            Map<Integer, Integer> countMap = new HashMap<>();
            boolean unique = true;
            for (int j = i; j < seq.length(); j++) {
                int count = countMap.getOrDefault(seq[j], 0);
                unique = (count == 1 || count == 0) ? false : true;
                countMap.put(seq[j], count + 1);
            }
            if (!unique) return false;
        }
        return true;

Part 4: Walkthrough

Here is a walkthrough the input, [1, 2, 1, 3, 2]. Each iteration will keep track of the idx i, and each subsequence generated at this starting left index.

i = 0:
[1]
[1,2]
[1,2,1]
[1,2,1,3]
[1,2,1,3,2]
Using countMap, we would have seen that each subsequence here has at least one unique element.
i = 1:
[2]
[2,1]
[2,1,3]
[2,1,3,2]
Using countMap, we would have seen that each subsequence here has at least one unique element.
i = 2:
[1]
[1,3]
[1,3,2]
Using countMap, we would have seen that each subsequence here has at least one unique element.
i = 3:
[3]
[3,2]
Using countMap, we would have seen that each subsequence here has at least one unique element.
i = 4:
[2]
Using countMap, we would have seen that each subsequence here has at least one unique element.

Since each possible subsequence is “good”, we can conclude this sequence itself is good.

Part 5: Runtime Analysis

As described above, the code uses two for loops to check each possible subsequence of seq. On the iteration of the first for loop, we create a HashMap, which allows us to check if each subsequence from the same start index has a unique element in amortized constant time. Overall, this results in time.