Check array in linear time with a constant space complexity Given an array of integers I have to return true if all the elements in the array are different or all the elements are the same. Otherwise, I have to return false.
E.g.
[1, 1, 1, 1] - all the elements are the same, so it is true
[12, 20, 1, 23] - all the elements are different, so it is also true
[12, 20, 1, 1] - we have just two 1, so it is false
The easy thing I was able to come up with is to use a hashmap to map an integer to a number of occurrences of that integer in the array. And then to iterate over the hashmap and check if there is at least one entry whose value is greater than 1 and is not equal to the length of the array, then I return false. Otherwise, I return true after the iteration.
The problem with my solution is that it has a linear space complexity and I feel that it should be possible to somehow solve the problem using a constant space complexity and linear time complexity.
So, could someone help me come up with an O(1) space complexity and O(n) linear complexity with respect to the array size solution, please?
I am working on this problem just for fun.
The problem does not have any $O(n)$ time algorithm. Note that it is easy to check in linear time if all the elements in the array are the same or not. However, to check if all the elements are district, the problem is known as Element distinctness problem. And, this problem has an $\Omega(n \log n)$ lower bound complexity. More technically, your problem can be reduced to element distinctness problem in linear time.
Therefore, the best possible solution here is $O(n \log n)$ time algorithm. For that, you can employ merge sort algorithm using a linked list. It also has an $O(1)$ space complexity.