refer to: https://www.algoexpert.io/questions/Largest%20Range
Problem Statement
Analysis
The most naive way, sort the array, then check the largest range, need O(nlogn) time complexity
Code
# step 1: store all the values in hashmap # step 2: iterate all the values in the array, for each value, check the range related to this value, how to check? check if the left/right number contains in the hashmap or not. # if in the hashmap, set the value of that key in the hashmap to False(visited), then we don't need to recheck those False values def largestRange(array): # Write your code here. bestRange = [] longestLength = 0 nums = {} # create a hashmap to store all the values, for num in array: nums[num] = True # initialize all to True(all values do not have been touched at first for num in array: if not nums[num]: continue # if set to false, the value has been explored, do nothing nums[num] = False # now, the current value is being explored currentLength = 1 # the currentLength is itself left = num - 1 right = num + 1 while left in nums: nums[left] = False currentLength += 1 left -= 1 # continue to explore the range from right to left while right in nums: nums[right] = False currentLength += 1 right += 1 # continue to expolre the range from left to right if currentLength > longestLength: longestLength = currentLength bestRange = [left + 1, right - 1] # at the end of the two while loops, right has been plus 1, left has been minus 1, need to restore the real values of left and right return bestRange
Time complexity: O(n) one pass for creating a hashmap, another pass for traversing each value in the array
Space complexity: O(n) store the hashmap
n is the length of the input array