Largest Range

• Time : O(n)
• Space : O(n)

#include <vector>
using namespace std;

vector<int> largestRange(vector<int> A) {
	int mi = *min_element(begin(A), end(A)), ma = *max_element(begin(A), end(A)), len = 0, n = A.size();
	int gap = -mi + 1;
	vector<int> merge(ma + gap + 2, 0);
	vector<int> res;
	
	for(int i = 0; i < n; i++) {
		int a = A[i] + gap, left = merge[a - 1], right = merge[a + 1];
		if(merge[a]) continue;
		merge[a] = merge[a - left] = merge[a + right] = right + left + 1;
		if(merge[a] > len) {
			len = merge[a];
			res = {a - left - gap, a + right - gap};
		}
	}
	
  // Write your code here.
  return res;
}