Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

681. Next Closest Time

Time: $O(1)$

Space: $O(1)$

			


class Solution {
 public:
  string nextClosestTime(string time) {
    const set<char> digitsSet{time[0], time[1], time[3], time[4]};
    string ans = time;

    ans[4] = nextClosest(digitsSet, ans[4], '9');
    if (time[4] < ans[4])
      return ans;

    ans[3] = nextClosest(digitsSet, ans[3], '5');
    if (time[3] < ans[3])
      return ans;

    ans[1] = nextClosest(digitsSet, ans[1], ans[0] == '2' ? '3' : '9');
    if (time[1] < ans[1])
      return ans;

    ans[0] = nextClosest(digitsSet, ans[0], '2');
    return ans;
  }

 private:
  char nextClosest(const set<char>& digitsSet, char digit, char limit) {
    auto it = digitsSet.upper_bound(digit);
    return it == end(digitsSet) || *it > limit ? *begin(digitsSet) : *it;
  }
};




			


class Solution {
  public String nextClosestTime(String time) {
    char[] ans = time.toCharArray();
    Character[] digits = {ans[0], ans[1], ans[3], ans[4]};
    TreeSet<Character> digitsSet = new TreeSet<Character>(Arrays.asList(digits));

    ans[4] = nextClosest(digitsSet, ans[4], '9');
    if (time.charAt(4) < ans[4])
      return new String(ans);

    ans[3] = nextClosest(digitsSet, ans[3], '5');
    if (time.charAt(3) < ans[3])
      return new String(ans);

    ans[1] = nextClosest(digitsSet, ans[1], ans[0] == '2' ? '3' : '9');
    if (time.charAt(1) < ans[1])
      return new String(ans);

    ans[0] = nextClosest(digitsSet, ans[0], '2');
    return new String(ans);
  }

  private char nextClosest(TreeSet<Character> digitsSet, char digit, char limit) {
    Character next = digitsSet.higher(digit);
    return next == null || next > limit ? digitsSet.first() : next;
  }
}




			


class Solution:
  def nextClosestTime(self, time: str) -> str:
    ans = list(time)
    digits = sorted(ans)

    def nextClosest(digit: chr, limit: chr) -> chr:
      next = bisect_right(digits, digit)
      return digits[0] if next == 4 or digits[next] > limit else digits[next]

    ans[4] = nextClosest(ans[4], '9')
    if time[4] < ans[4]:
      return ''.join(ans)

    ans[3] = nextClosest(ans[3], '5')
    if time[3] < ans[3]:
      return ''.join(ans)

    ans[1] = nextClosest(ans[1], '3' if ans[0] == '2' else '9')
    if time[1] < ans[1]:
      return ''.join(ans)

    ans[0] = nextClosest(ans[0], '2')
    return ''.join(ans)