7-liner "O(1)" solution: only 60*24 possible different time points!


  • 1

    Note that there are only maximum 60*24 different time point strings, so we definitely get duplicates if there are more than 60*24 time points, i.e., answer is simply zero! So the essential size of this problem is upper bounded by constant 60*24.

        int findMinDifference(vector<string>& times) {
          if (times.size() > 60*24) return 0; // must have duplicates!
          sort(times.begin(), times.end()); // sort times in ascending order
          
          int minDiff = INT_MAX, pre = timeToInt(times.back()) - 60*24; // previous time in minutes
          for (auto& t:times)
            minDiff = min(minDiff, timeToInt(t)-pre), pre = timeToInt(t);
          return minDiff;
        }
        
        // convert time point string to int of minutes
        int timeToInt(const string& t) {
          return 60*stoi(t.substr(0,2)) + stoi(t.substr(3,2));    
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.