Monday, 14 September 2020

Find longest length bi-valued slice in an array

Find longest length bi-valued slice in an array in java

This is a popular interview question asked in Tier-1 companies.

You are given a sequence of n integers and the task is to find the maximum slice of the array which contains no more than two different numbers.

Example:
1. Input: [1, 2, 1, 2, 2, 3, 3, 2, 3]
Output: 6
Max slice is [2, 2, 3, 3, 2, 3] which contains only two numbers 2 and 3 and the length is 6 

2. Input: [1, 2, 3]
Output: 2
Max slice is either [1, 2] or [2, 3] which contains only two numbers and the length is 2

3. Input: [1, 4, 4, 1, 4]
Output: 5 
Max slice is whole array which contains only two numbers 1 and 4 and the length is 5

4. Input: [2]
Output: 1 
Max slice is whole array which contains only one number 2 and the length is 1

Algorithm

As we are looking for bi-value slice, we will keep two pointer lastSeen and secondLastSeen which keep track of the numbers we last read.

So if the current number we are reading is one of the number we read before that is it is same as either lastSeen or secondLastSeen, then we can increase our longest bi-value slice counter(say tempCounter) by 1

So we have three variables till now, lastSeen, secondLastSeen and tempCounter to store the current longest bi-value slice.


Consider the array [1, 2, 1, 2, 2, 3, 3, 2, 3]

say we read 1, 2, 1, 2, 2 and we were good at that point, now we read element 3, so in that case new series has started but including the current number 3 we can include the previous two 2's in this series that is starting from index 3.

So instead of going back and see the last repeated number, we will keep track of this in the separate variable lastSeenNumberRepeatedCount which holds the number of times last seen value repeated in this case lastSeenNumberRepeatedCount would be 2, because when we encountered 3 at index 5, the number before 3 is 2 which first occur at index 3 and then the same number repeated that is lastSeen number repeated at index 4 so making lastSeenNumberRepeatedCount to 2.

So when we encounter 3 at index 5, we directly add the lastSeenNumberRepeatedCount to our tempCounter so it would be lastSeenNumberRepeatedCount + 1 (added 1 because starting from 3 new series has started, so including the current number 3)

So we have four variables till now, lastSeen, secondLastSeen, tempCounter and lastSeenNumberRepeatedCount.

We also need one more variable for storing our longest bi-valued slice as tempCounter will change when new series starts so what about the previous value of tempCounter which was our last longest bi-value slice till that point.

So we have five variables till now, lastSeen, secondLastSeen, tempCounter, lastSeenNumberRepeatedCount and lbs for storing result.

Java Program to find largest bi-valued slice in an array

package javabypatel;

public class LongestBiValueSlice {
    public static void main(String[] args) {
        System.out.println(new LongestBiValueSlice().getLongestSlice(new int[]{2}));
    }

    public int getLongestSlice(int[] arr) {
        int lastSeen = -1;
        int secondLastSeen = -1;
        int lbs = 0;
        int tempCount = 0;
        int lastSeenNumberRepeatedCount = 0;

        for (int current : arr) {
            if (current == lastSeen || current == secondLastSeen) {
                tempCount ++;
            } else {
                // if the current number is not in our read list it means new series has started, tempCounter value in this case will be
                // how many times lastSeen number repeated before this new number encountered + 1 for current number.
                tempCount = lastSeenNumberRepeatedCount + 1;
            }

            if (current == lastSeen) {
                lastSeenNumberRepeatedCount++;
            } else {
                lastSeenNumberRepeatedCount = 1;

                secondLastSeen = lastSeen;
                lastSeen = current;
            }

            lbs = Math.max(tempCount, lbs);
        }
        return lbs;
    }
}
at

No comments:

Post a Comment