Given an array a[0..N-1] of integers between 0 < N < 10^5, find the size of the longest most repeated subarray in optimal time and space. I was thinking of using a HashMap to store the indexes where a number begins, and start checking for each index the possible subarrays it can form. But this seems inefficient, so I would like to hear some opinions of how I can approach this problem.
Example:
Input a = [0,1,2,1,4,1,2,1,0,5]
Expected output: Most Repeated: [1,2,1]; Size: 3
Such problems are known to have a naive approach - something that takes a lot of time and performs a brute force search for all the possible solutions.
Obviously, you are not looking for that. Whenever you are in such a situation, the answer is always Dynamic Programming. It is a fairly broad, difficult for beginners and very important in computer science. Which means, I cannot cover it in this answer.
But here is one approach on how you can solve this problem.
Since a common subarray of A and B must start at some A[i] and B[j], let dp[i][j] be the longest common prefix of A[i:] and B[j:]. Whenever A[i] == B[j], we know dp[i][j] = dp[i+1][j+1] + 1. Also, the answer is max(dp[i][j]) over all i, j.
We can perform bottom-up dynamic programming to find the answer based on this recurrence. Our loop invariant is that the answer is already calculated correctly and stored in dp for any larger i, j.
Hope this helps. Good luck.