Search code examples
arraysalgorithmrotationsubsequence

Longest sub array in rotating array

Is there any way to find the longest subarray of 1's in log(n) time?

example:

  1. 110011111000 - then the output is 5 (from pos 5 to 10)

  2. 1110011101 - the output here is 3 but after rotation 1 the array becomes 111100111 and the output is now 4.

  3. 001111 - the output here is 4 from pos 3 to 6 but after rotation it becomes 3 from pos 4 to 6

Note: I found the longest subarray length in O(n) before rotation. How can I improve the solution after rotation if I have the past results?

Solution

  • You can follow those steps:

    1. find the longest subarray of 1 (in O(n)). During that loop find the first and last instance of 0.
    2. Start rotating and update those parameters.
    3. If the last index is 0 search for the previous 1 to keep updated the parameters (at complexity this will not go over O(n) total.

    I will assume you know how to get max subarray index and count in O(n). In addition to that, you will need to find the second largest subarray (can be done in the same loop).

    Let extract 2 more params - first and last zeros (Simple code - I can attach it if you need )

    When you rotate the array there are 3 option:

    1. Nothing change
    2. Bigger subarray created
    3. Current biggest subarray breaks

    In the first and second cases - you only need to update the params - O(1) - you can know this is the case according your params. In the third, you will need to use the second longest subarray you find (notice that only 1 subarray can be break at a time)

    For example, consider you have array: 1110011101 (as your example) and you have max = 3 and maxIndex = 5. After running the getZeroIndexs function you also know that firstZeroIndex = 3 and lastZeroIndex = 8.

    How our var will look like after rotate? 

    max = 3
maxIndex = 6
firstZeroIndex = 4 // this will increase as long as the lastZeroIndex different then the array size
lastZeroIndex = 9 //this will go up till array.size - when it those you need to loop again till you find last

    In this case, the first index move to 4 whats make him bigger then max -> max = 4 and maxIndex = 0.

    Now your array is : 1111001110 so lastZeroIndex = 9 as the array size so next rotation will yield:

    max = 4
maxIndex = 1
firstZeroIndex = 0 
lastZeroIndex = ? // here you need to loop from the end of your array till you get 0 -> O(k) in total complexity, all the run together will be O(n)

    Hope it clear, if not feel free to ask!