Circular arrays — The chicken or the egg debate!
Dealing with problems involving circular arrays can get pretty tricky, in this article I’ll cover a few different strategies to handle them.
- One way to handle circular arrays is to think of the solution as being either within a straight array or being shared between two arrays
Take maximum sum subarray problem for a circular array, the solution will be maximum of case1, which is just finding the maximum sum subarray in a straight array, and case 2, which can be computed by computing the minimum sum subarray for a straight array and subtracting it from the total sum of the array.
2. Fixing a start if possible
Let’s look at finding the next greater element for a circular array, we need to find the start point, which would be the largest element in the array as that will always have the next greater as -1.
Another example would be the house robber problem. we consider two cases, robbing the first house, in this case, we can traverse just till the second last index. The second case is not robbing the first house, this is now a straight array solution starting from the second index till the end of the array.
3. Wrap around the array
This is kind of like a sliding window solution.
The basic structure of the solution is to find the first window and then basically increase the end one by one, and for every increase of the end, check if the start needs to be updated to make the window valid again.
Here we can have the start as the end (n -1) and end as the start 0, so we consider extending the end till the problem property is violated, and we try to decrease the start till the violation is removed, this way we wrap around the array in a circular fashion.
Hope this article helped you folks consolidate some ideas around dealing with circular arrays, please feel free to comment if you have more ways to add to the list!
Thanks for reading!
