Length of maximum continuous subarray with 2 unique numbers

user_10578541 0
Viewed 907

I have an array of numbers and I want to figure out the maximum length of a continuous subarray of 2 unique numbers repeating.

For example, [2, 3, 4, 3, 2, 2, 4] would return 3 since [3, 2, 2] is of length 3.

[2, 4, 2, 5, 1, 5, 4, 2] would return 3.
[7, 8, 7, 8, 7] would return 5.

Edit: I have considered an O(n^2) solution where I start at each value in the array and iterate until I see a third unique value. 

for item in array:
    iterate until third unique element
    if length of this iteration is greater than existing max, update the max length
return maxlength

I do not, however, think this is an efficient solution.

vector data-structures algorithm
3 Answers

It can be done O(n). The code is in python3. o and t are one and two respectively. m is the max and c is the current count variable.

a = [7, 8, 7, 8, 7]
m = -1
o = a[0]
t = a[1]
# in the beginning one and two are the first 2 numbers 
c = 0
index = 0
for i in a:
    if i == o or i == t:
        # if current element is either one or two current count is increased
        c += 1
    else:
        # if current element is neither one nor two then they are updated accordingly and max is updated
        o = a[index - 1]
        t = a[index]
        m = max(m, c)
        c = 2
    index += 1
m = max(m, c)

print(m)
user_85779170

We can use two pointer technique to solve this problem in O(n) run time complexity. These two pointer for example startPtr and endPtr will represent the range in the array. We will maintain this range [startPtr, endPtr] in such way that it contains no more than 2 unique number. We can do this by keeping track of position of the 2 unique number. My implement in C++ is given below:

int main()
{
    int array[] = {1,2,3,3,2,3,2,3,2,2,2,1,3,4};
    int startPtr = 0;
    int endPtr = 0;

    // denotes the size of the array
    int size= sizeof(array)/sizeof(array[0]);

    // contain last position of unique number 1 in the range [startPtr, endPtr] 
    int uniqueNumPos1 = -1; // -1 value represents it is not set yet

    // contain last position of unique number 2 in the range [startPtr, endPtr]
    int uniqueNumPos2 = -1; // -1 value represents it is not set yet


    // contains length of maximum continuous subarray with 2 unique numbers
    int ans = 0;

    while(endPtr < size) {
        if(uniqueNumPos1 == -1 || array[endPtr] == array[uniqueNumPos1]) {
            uniqueNumPos1 = endPtr;
        }
        else {
            if(uniqueNumPos2 == -1 || array[endPtr] == array[uniqueNumPos2]) {
                uniqueNumPos2 = endPtr;
            }
            else {
                // for this new third unique number update startPtr with min(uniqueNumPos1, uniqueNumPos2) + 1
                // to ensure [startPtr, endPtr] does not contain more that two unique
                startPtr = min(uniqueNumPos1, uniqueNumPos2) + 1;

                // update uniqueNumPos1 and uniqueNumPos2
                uniqueNumPos1 = endPtr -1;
                uniqueNumPos2 = endPtr;
            }
        }

        // this conditon is to ensure the range contain exactly two unique number
        // if you are looking for the range containing less than or equal to two unique number, then you can omit this condition
        if (uniqueNumPos1 != -1 && uniqueNumPos2 !=-1) {
            ans = max( ans, endPtr - startPtr + 1);
        }

        endPtr++;
    }

    printf("%d\n", ans);
}

Thanks @MBo for pointing out the mistakes.

user_68787080 
import java.util.Arrays;
import static java.lang.System.out;
class TestCase{
    int[] test;
    int answer;
    TestCase(int[] test,int answer){
        this.test = test;
        this.answer = answer;
    }
}
public class Solution {
    public static void main(String[] args) {
        TestCase[] tests = {
                            new TestCase(new int[]{2, 3, 4, 3, 2, 2, 4},3),
                            new TestCase(new int[]{2, 3, 3, 3, 3, 4, 3, 3, 2, 2, 4},7),
                            new TestCase(new int[]{1,2,3,3,4,2,3,2,3,2,2,2,1,3,4},7),
                            new TestCase(new int[]{2, 7, 8, 7, 8, 7},5),          
                            new TestCase(new int[]{-1,2,2,2,2,2,2,2,2,2,2,-1,-1,4},13),
                            new TestCase(new int[]{1,2,3,4,5,6,7,7},3),
                            new TestCase(new int[]{0,0,0,0,0},0),
                            new TestCase(new int[]{0,0,0,2,2,2,1,1,1,1},7),
                            new TestCase(new int[]{},0)
        };

        for(int i=0;i<tests.length;++i){
            int ans = maxContiguousArrayWith2UniqueElements(tests[i].test);
            out.println(Arrays.toString(tests[i].test));
            out.println("Expected: " + tests[i].answer);
            out.println("Returned: " + ans);
            out.println("Result: " + (tests[i].answer == ans ? "ok" : "not ok"));
            out.println();
        }         
    }

    private static int maxContiguousArrayWith2UniqueElements(int[] A){
        if(A == null || A.length <= 1) return 0;
        int max_subarray = 0;
        int first_number = A[0],second_number = A[0];
        int start_index = 0,same_element_run_length = 1;
        for(int i=1;i<A.length;++i){
            if(A[i] != A[i-1]){ 
                if(first_number == second_number){
                    second_number = A[i];
                }else{
                    if(A[i] != first_number && A[i] != second_number){
                        max_subarray = Math.max(max_subarray,i - start_index); 
                        start_index = i - same_element_run_length;
                        first_number  = A[i-1];
                        second_number = A[i];
                    }
                }
                same_element_run_length = 1;
            }else{
                same_element_run_length++;
            }
        }

        return first_number == second_number ? max_subarray : Math.max(max_subarray,A.length - start_index);
    }
}

OUTPUT:

[2, 3, 4, 3, 2, 2, 4]
Expected: 3
Returned: 3
Result: ok

[2, 3, 3, 3, 3, 4, 3, 3, 2, 2, 4]
Expected: 7
Returned: 7
Result: ok

[1, 2, 3, 3, 4, 2, 3, 2, 3, 2, 2, 2, 1, 3, 4]
Expected: 7
Returned: 7
Result: ok

[2, 7, 8, 7, 8, 7]
Expected: 5
Returned: 5
Result: ok

[-1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, -1, -1, 4]
Expected: 13
Returned: 13
Result: ok

[1, 2, 3, 4, 5, 6, 7, 7]
Expected: 3
Returned: 3
Result: ok

[0, 0, 0, 0, 0]
Expected: 0
Returned: 0
Result: ok

[0, 0, 0, 2, 2, 2, 1, 1, 1, 1]
Expected: 7
Returned: 7
Result: ok

[]
Expected: 0
Returned: 0
Result: ok

Algorithm:

  • So, we maintain 2 variables first_number and second_number which will hold those 2 unique numbers.
  • As you know, there could be many possible subarrays we have to consider to get the max subarray length which has 2 unique elements. Hence, we need a pointer variable which will point to start of a subarray. In this, that pointer is start_index.
  • Any subarray breaks when we find a third number which is not equal to first_number or second_number. So, now, we calculate the previous subarray length(which had those 2 unique elements) by doing i - start_index.
  • Tricky part of this question is how to get the start_index of the next subarray.
  • If you closely observe, second_number of previous subarray becomes first_number of current subarray and third number we encountered just now becomes second_number of this current subarray.
  • So, one way to calculate when this first_number started is to run a while loop backwards to get that start_index. But that would make the algorithm O(n^2) if there are many subarrays to consider(which it will be).
  • Hence, we maintain a variable called same_element_run_length which just keeps track of the length or frequency of how many times the number got repeated and gets updated whenever it breaks. So, start_index for the next subarray after we encounter the third number becomes start_index = i - same_element_run_length.
  • Rest of the computation done is self-explanatory.
  • Time Complexity: O(n), Space Complexity : O(1).
user_49648220
Related