C++ different approach using buckets (easy to understand)


  • 0
    class Solution {
        string format(int hrs, int min){
            string res="";
            res += ((hrs<10)?"0"+to_string(hrs):to_string(hrs));
            res += ":";
            res += ((min<10)?"0"+to_string(min):to_string(min));
            return res;
        }
    public:
        string nextClosestTime(string time) {
            //get the original hrs and mins 
            int hrs = stoi(time.substr(0, 2));
            int mins = stoi(time.substr(3));
            
            //create buckets for hr and min
            vector<char> hr(24, false);
            vector<char> min(60, false);
            
            vector<int> arr(4);
            arr[0] = (time[0]-'0');
            arr[1] = (time[1]-'0');
            arr[2] = (time[3]-'0');
            arr[3] = (time[4]-'0');
            
            //generate all combinations of the digits and fill the buckets
            for (int i=0;i<4;i++){
                for (int j=0;j<4;j++){
                    int num = arr[j]*10 + arr[i];
                    if (num<24) hr[num] = true;
                    if (num<60) min[num] = true;
                }
            }
            
            //if any minute after the given minute can be formed using the given digits return 
            for (int i=mins+1;i<60;i++){
                if (min[i]==true){
                    return format(hrs, i);
                }
            }
            
            //if not then find the minute that is farthest from the current minute
            int newMin=-1;
            for (int i=0;i<mins;i++){
                if (min[i]==true){
                    newMin = i;
                    break;
                }
            }
            
            if (newMin==-1) return time;
            
            //find the hour that is closest and after the given hours
            int newHr=-1;
            for (int i=hrs+1;i<24;i++){
                if (hr[i]==true){
                    newHr = i;
                    return format(newHr, newMin);
                }
            }
            
            //if not find the one that is closest to the given hours
            for (int i=hrs-1;i>=0;i--){
                if (hr[i]==true){
                    newHr = i;
                    return format(newHr, newMin);
                }
            }
            
            //if neither exists return the original i.e newHr==-1 && newMin==-1
            return time;
        }
    };
    

Log in to reply
 

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