04/05/2018

[Java] Summarize a TreeSet

Given a TreeSet of Integers, return a string representation according to the following rules:
  • if N is in the TreeSet but N-1 and N+1 are not, return N and comma separate it from the rest
  • if N is in the TreeSet and N-1 or N+1 are too, return a dashed range
eg:
1,5,9 should output 1,5,9
1,2,4,5,6,7,8 should output 1-2,4-8

The idea is to track an item while iterating over the TreeSet in ascending order and tracking whether the current item is part of a range - it is if it's equal to the tracked item + 1.
When we encounter an item that breaks the current range, we check the rules and determine what to print, either a range or a single item.

Note: at the end of the iteration it is still important to check if the last element (yet unprocessed) was part of a range or not and in case add it to the result.

Runtime is O(N) and space is O(1).

You can check my implementation of summarize on my Gist alongside some test cases in TreeSetJTests.

No comments:

Post a Comment

With great power comes great responsibility.

Da grandi poteri derivano grandi responsabilità.