Summary Ranges: using two pointers to return summary of an array

This was asked in Google interview.

Given a sorted integer array without duplicates, return the summary of its ranges.

For example, given [0,1,2,4,5,7], return ["0->2","4->5","7"].

My Solution

The idea is using two pointers to maintaining the start index and end index, then format it correctly. If the start and end index are the same, format it without the arrow, otherwise add arrow in between. The time complexity would be O(n) and the space is O(n) since I use extra space array to store the result.

def summary_range(nums):
  if not nums:
    return []
  start, i, res = 0, 0, []
  while i<len(nums)-1:
    if nums[i+1]-nums[i] != 1:
      format_range(res, nums, start, i)
      start = i+1
    i += 1
  # for the last element or in case of 1 element
  format_range(res, nums, start, i)
  return res

def format_range(res, nums, start, end):
  if start == end:
    res.append(str(nums[start]))
  else:
    res.append(str(nums[start]) + "->" + str(nums[end]))

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s