[C++] Clean Code


  • 8
    class Solution {
    public:
        int findMinDifference(vector<string>& times) {
            int n = times.size();
            sort(times.begin(), times.end());
            int mindiff = INT_MAX;
            for (int i = 0; i < times.size(); i++) {
                int diff = abs(timeDiff(times[(i - 1 + n) % n], times[i]));
                diff = min(diff, 1440 - diff);
                mindiff = min(mindiff, diff);
            }
            return mindiff;
        }
    
    private:
        int timeDiff(string t1, string t2) {
            int h1 = stoi(t1.substr(0, 2));
            int m1 = stoi(t1.substr(3, 2));
            int h2 = stoi(t2.substr(0, 2));
            int m2 = stoi(t2.substr(3, 2));
            return (h2 - h1) * 60 + (m2 - m1);
        }
    };
    

  • 0

    @alexander nice a simple, but this will be O(n log n) due to sorting. If you plot the minutes on a line (bool array) then check the line you can reduce this to O(n). You can do this because there are not that many minutes in a day and so the bool array size will be relatively small. Check out some of the other posts to see how it's done.


  • 0
    F

    Although not the optimal solution, but i like the line :abs(timeDiff(times[(i - 1 + n) % n], times[i]));


  • 0
    I

    I think in the first line of the for loop, if you wrote times[(n - 1 + i) % n], times[i] would be easier to understand


  • 0
    J

    @ian34 probably not, i-1 is prev index, (i-1+n)%n is simply tring to looping it circularly without "if", i.e. last element will get first element as prev element.

    The extra price is "abs". I doubt it will run faster compared to "if" version. The optimal one should set prev to last element before loop.


  • 0
    Z

    @jdrogin If adding 1 line, this could be an O(n) solution. The line is " if (n > 1440) return 0;". See the code below.
    When n <= 1440, it is O(log2(1440) n), i.e. O(n). The run time is 12 ms, currently beating 97.71%.

    class Solution {
    public:
        int findMinDifference(vector<string>& timePoints) {
            int n = timePoints.size();
            if (n > 1440) return 0;
            vector<int> times;
            for (int i = 0; i < n; i++) 
                times.push_back(to_min(timePoints[i]));
            sort(times.begin(), times.end());
            int ans = times[0]+60*24-times.back();
            for (int i = 1; i < n; ++i) {
                ans = min(ans, times[i]-times[i-1]);
            }
            return ans;
        }
    private:
        int to_min(string& a) {
            int h = (a[0]-'0')*10+(a[1]-'0'), m = (a[3]-'0')*10+(a[4]-'0');
            return 60*h+m;
        }
    };
    

Log in to reply
 

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