Jan 2

LC-961: N-Repeated Element in Size 2N Array (Rust)

My initial approach was to keep an hashmap of scores. The [number, no_of_times]. After then, I can loop over the nums array, and add to my hashmap.
	Then after, I convert to a Vec of tuples, sort descending, to get the most frequent element first and return it.
	
```
use std::collections::HashMap;

impl Solution {
	pub fn repeated_n_times(nums: Vec<i32>) -> i32 {
			let mut scores = HashMap::with_capacity(nums.len());

			for n in nums {
					*scores.entry(n).or_insert(0) += 1;
			}

			let mut hash_vec : Vec<(&i32, &i32)> = scores.iter().collect();
			hash_vec.sort_by(|a,b| b.1.cmp(a.1));

			*hash_vec[0].0
	}
}
```

Time Complexity: O(n log n) - dominated by the sort
Space Complexity: O(n) - HashMap + Vec

Time was good, not the best. Further optimization now:
```
use std::collections::HashMap;

impl Solution {
    pub fn repeated_n_times(nums: Vec<i32>) -> i32 {
        let mut scores = HashMap::with_capacity(nums.len());
        let target = nums.len()/2;

        for &n in &nums {
            let count = scores.entry(n).or_insert(0);
            *count += 1;

            if *count == target {
                return n;
            }
        }

        unreachable!()
    }
}
```

The problem states that exactly one element appears n times where n = array.length / 2. This means:

- We don't need ALL frequencies
- We don't need to sort
- We can return as soon as we find an element that hits the target count!

Time Complexity: O(n) - single pass, no sort
Space Complexity: O(n) - just the HashMap

I thought of a sliding window approach further, which I think might still not be the best solution for some arrays but it passes excellently: it will fail this:  [1,3,3,2,2,4,5,2,2,2,1,2]

```
impl Solution {
    pub fn repeated_n_times(nums: Vec<i32>) -> i32 {

        for n in 0..nums.len() - 2 {
            if nums[n] == nums[n+1] || nums[n] == nums[n+2] {
                return nums[n];
            }

            if nums[n+1] == nums[n+2] {
                return nums[n+1];
            }
        }

        nums[nums.len() - 1]
    }
}
```
It's checking windows of 3 consecutive elements as it slides through the array. 
Let's say you have an array of length `n`, and `n/2` elements are the number `X`:
Check if elements at distance 1 or 2 are the same, Check if the next two elements match, else return the last element (worst case).

Time: 0(n)
Space: 0(1)