EPIJ (2017 ed) - 5.6 variant 1- Find length of longest subarray with equal entries

#1

The solution I’m considering seems so simple that I’m wondering if I’m interpreting the problem correctly.

The problem is: Write a program that takes an array of integers and finds the length of a longest subarray all of whose entries are equal.

The solution I have in mind is to walk the array, maintaining a map of counts of unique entries. The longest value in the map is the length of the longest subarray. Time complexity O(n), space complexity O(n).

Is this a correct approach?

Also, may I assume that the entries in the longest subarray are not necessarily stored at contiguous indices in the original array?

Thanks!

0 Likes
#2

This post answers the second question (about whether the subarrays are continguous).

But I’d still like to know if the problem can be solved with better than time complexity O(n) and space complexity O(n).

0 Likes
#3

Figured out a better approach - yes, this can be done in time O(n) and space O(1).

0 Likes