## Thursday, May 10, 2018

### LeetCode 697 - Degree of an Array

https://leetcode.com/problems/degree-of-an-array/description/
Given a non-empty array of non-negative integers `nums`, the degree of this array is defined as the maximum frequency of any one of its elements.
Your task is to find the smallest possible length of a (contiguous) subarray of `nums`, that has the same degree as `nums`.
Example 1:
```Input: [1, 2, 2, 3, 1]
Output: 2
Explanation:
The input array has a degree of 2 because both elements 1 and 2 appear twice.
Of the subarrays that have the same degree:
[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
The shortest length is 2. So return 2.
```
Example 2:
```Input: [1,2,2,3,1,4,2]
Output: 6
```
Note:
• `nums.length` will be between 1 and 50,000.
• `nums[i]` will be an integer between 0 and 49,999.

• ```    public int findShortestSubArray(int[] nums) {
Map<Integer, Integer> left = new HashMap(),
right = new HashMap(), count = new HashMap();

for (int i = 0; i < nums.length; i++) {
int x = nums[i];
if (left.get(x) == null) left.put(x, i);
right.put(x, i);
count.put(x, count.getOrDefault(x, 0) + 1);
}

int ans = nums.length;
int degree = Collections.max(count.values());
for (int x: count.keySet()) {
if (count.get(x) == degree) {
ans = Math.min(ans, right.get(x) - left.get(x) + 1);
}
}
return ans;
}
```
public int findShortestSubArray(int[] nums) {
Map<Integer, Element> map = new HashMap<>();
int max = scan(nums, map);
int result = Integer.MAX_VALUE;

for (Element el : map.values()) {
if (el.count == max) {
// 1,2
result = Math.min(result, el.lastPos - el.firstPos + 1);
}
}
return result;
}

private int scan(int[] nums, Map<Integer, Element> map) {
int max = 0;
for (int i = 0; i < nums.length; i++) {
int value = nums[i];
Element el = map.get(value);
if (el == null) {
el = new Element(i, i, 1);
map.put(value, el);
} else {
el.lastPos = i;
el.count++;
}

max = Math.max(max, el.count);
}
return max;
}

private static class Element {
public int firstPos, lastPos, count;

public Element(int firstPos, int lastPos, int count) {
super();
this.firstPos = firstPos;
this.lastPos = lastPos;
this.count = count;
}
}