LeetCode 441: Arranging Coins Solution

Problem Statement could be found @https://leetcode.com/contest/11/problems/arranging-coins/


Code Snippet - Code, I believe, is self explainatory

class Solution {
public:
    int arrangeCoins(int n) {
       int i = 1;
       if (n ==0)
        return 0;
       while ( (n-i) >=0){
           n = n-i;
           i++;
         
       }
     
       return (i-1);
    }
};

Leetcode 3: Longest Substring Without Repeating Characters

Problem statement could be found @https://leetcode.com/problems/longest-substring-without-repeating-characters/

Code Snippet -


class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        long start = 0;
        long current =0;
        long arr[256];
        for (int i=0;i<256;i++)
            arr[i]= -1;
        int maxL = 0;
       
        while(current < s.size()){
            int x = s.at(current);
         
            // if character has already occurred
            if (arr[x] != -1 ){
                // if the current character, has just repeated
                if ( ( arr[x] +1) == current){
                    start = current;
                }else{
                    // to handle string like "abcdbx", here second occurence of b changes the start index
                    if (start <= arr[x])
                        start = arr[x] +1;
                   
                }
            }
            if ((current-start+1) > maxL){
                 maxL = current-start+1;
            }
            arr[x] = current;
           
            current++;
        }
     
        return maxL;
    }
};

Leetcode 2: Add Two Numbers Solution

Problem statement could be found @https://leetcode.com/problems/add-two-numbers/

Solution-

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
       
        if (l1 == NULL)                                
            return l2;
        if (l2 == NULL)
            return l1;
       
        ListNode *sNode = new ListNode((l1->val+l2->val)%10);              
        int carry = (l1->val+l2->val)/10;
        ListNode *temp = sNode;
        l1 = l1->next;
        l2= l2->next;
       
        while (l1 != NULL && l2!=NULL){
           int v = l1->val+l2->val + carry;  
           temp->next = new ListNode(v%10) ;
           carry = v/10;
           temp = temp->next;
           l1 = l1->next;
           l2 = l2->next;
        }
        ListNode *p = NULL;
        if (l1 == NULL && l2 !=NULL){
            p = l2;
        }
        if (l2 == NULL && l1 !=NULL){
            p = l1;
        }  
        while (p!=NULL){
           int v = p->val+ carry;  
           temp->next = new ListNode(v%10) ;
           carry = v/10;
           temp = temp->next;
           p = p->next;
         
        }
        if (carry !=0){
            temp->next = new ListNode(carry);
        }
        return sNode;
    }                                                                                                                                                          
   
};

Status - Accepted by Leetcode

Leetcode 1: Two Sum Solution

Problem statement could be found @https://leetcode.com/problems/two-sum/


Code Snippet -

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> retVec;
        int vSize = nums.size();
        for (int i=0;i<vSize;i++){
            int cur = nums[i];
            for (int j=(i+1);j<vSize;j++){
             
                if ((cur + nums[j]) == target){
                     retVec.push_back(i);
                    retVec.push_back(j);
                     return retVec;
                }
            }
        }
          return retVec;
    }
};

Status - Accepted
Runtime: 386 ms

Leetcode 437: Path Sum III Solution

Problem Statement could be found @https://leetcode.com/problems/path-sum-iii/

Solution -
Idea is to save the sum of all intermediate nodes  from Root Node to a given node. Try adding the value of current nodes to all the stored values and compare it with the required value. To store all required value we can use stack. Here, I'm using vector to implement Stack

Following is the code which is accepted by Leetcode. It took 138 msec to execute 126 test cases

class Solution {
    int count;
    int k;
public:
    void trav(TreeNode *root, vector<int> s){
        if (root == NULL){
            return;
        }
        if (root->val == k){
            count++;
        }
        vector<int> temp;
        for (int i=0;i<s.size();i++){
            if ((s[i] + root->val) == k){
                count ++;
               
            }
            temp.push_back(s[i] + root->val);
        }
        temp.push_back(root->val);
        trav(root->left, temp);
        trav(root->right, temp);
        temp.pop_back();
    }
    int pathSum(TreeNode* root, int sum) {
        count = 0;
        k = sum;
        vector<int> s;
        trav(root, s);
        return count;
    }
};

Solution to Leetcode 423: Reconstruct Original Digits from English

Problem statement could be found @https://leetcode.com/problems/reconstruct-original-digits-from-english/


Thought process -

The first approach that came to my mind was recursion + backtracking, but given the length of input string could go upto 50,000 there was a high possibility of the solution giving timeout.

Next I started thinking of unique properties of the number strings, there is realized there some unique characters in number like
1. x in six, x does not occur in any other number
2. w in two, w also does not occur in any other number
3. u in four, u doesn't occur in any other number
4. Similarly, z in zero & g in eight

So it is extremely easy to identify number like two,six, four, zero and eight. But what about other numbers? So, lets see what are the remaining numbers
one, three,  five,  seven, nine.

Lets check the uniqueness in above numbers
1. o in one
2. t in Three
3. s in Seven
4. f in Five
5. i in Nine

Hence, finding the count of o, t, s, f and i, we  can get remaining characters.

Following is the code, the solution is accepted by Leetcode and runs in 26 msec for all testcases

class Solution {
    map<char, string> uDict;
    map<char, int> uMap;
 
    map<char, string> sDict;
    map<char, int> sMap;
    int handled;
    int toHandle ;
public:
    void uDigit(){
        uDict['z'] = "zero";
        uDict['w'] = "two";
        uDict['g'] = "eight";
        uDict['u'] = "four";
     
        uDict['x'] = "six";
     
        uMap['z'] = 0;
        uMap['w'] = 2;
        uMap['g'] = 8;
        uMap['u'] = 4;
   
        uMap['x'] = 6;
     
    }
 
    void sDigit(){
        sDict['t'] = "three";
        sDict['o'] = "one";
        sDict['s'] = "seven";
        sDict['i'] = "nine";
        sDict['f'] = "five";
        sMap['t'] = 3;
        sMap['o'] = 1;
        sMap['s'] = 7;
        sMap['i'] = 9;
        sMap['f'] = 5;
    }
 
    bool  rem(int arr[], int count, string str){
        for (auto s=str.begin(); s != str.end();s++){
            if ( arr[*s-'a']  < count )
                return false;
         
        }
        for (auto s=str.begin(); s != str.end();s++){
            arr[*s-'a']  =  arr[*s-'a'] - count;
         
        }
        handled = handled+ str.size() * count;
        return true;
    }
 
    void tryUMap(int arr[],int op[],
        map<char, string> &dict, map<char, int> &numMap){
            for (auto x = dict.begin(); x!= dict.end(); x++){
                if (handled == toHandle)
                    return ;
                if (arr[x->first-'a'] != 0){
                     int count = arr[x->first-'a'] ;
                    if ( rem(arr, count, x->second) == true){
                     
                        op[numMap[x->first] ] = op[numMap[x->first] ] + count;
                    }
                 
                 
                }
            }
        }
 
    string originalDigits(string s) {
        handled = 0;
        uDigit();
        sDigit();
        int arr[26] = {0};
        toHandle = s.size();
   
        for (int i=0;i<s.size();i++){
            arr[s.at(i) - 'a'] ++;
        }
        int op[10] = {0};
     
     
        tryUMap(arr,op,uDict, uMap);
     
        tryUMap(arr,op,sDict, sMap);
        std::ostringstream oss;
        string os="";
        for (int i=0;i<10;i++){
            while (op[i] != 0){
                oss <<i;
                op[i]--;
            }
        }
       return oss.str();
    }
};

Solution to leetcode 315 Count of Smaller Numbers After Self

Problem statement could be found @https://leetcode.com/problems/count-of-smaller-numbers-after-self/

Analysis
This problem can have another form where one is asked to find number of inversions.

Approach
Use merge sort technique ie divide collection (here vector) into smaller parts and count inversions.

Following is the code -
1. Here I'm using a map to count inversions for an integer, hence the limitation of this code it doesn't work with duplicates.
2. Another important point is I'm filling the greatest element in vector first during merge. It helps simplify the code by following logic. So if an element is left half is larger than current element of right half, then following formula gives the count of element in right half with which left element is larger

   valMap[nums[leftBoundary]] = valMap[nums[leftBoundary]] +
                                                                  (rightBoundary - right + 1);

We could have tried filling smaller element first, in that case finding inversions would have taken a for loop.


class Solution {
    map<int, int> valMap;
private:
    void applyMerge(vector<int> &nums, int startIndex, int endIndex){
        if (startIndex >= endIndex){
            return ;
        }
       
        int midIndex = (startIndex+endIndex)/2;
        applyMerge(nums, startIndex, midIndex);
        applyMerge(nums, (midIndex+1),endIndex);
       
        int left = startIndex;
        int right = midIndex+1;
        int leftBoundary = midIndex;
        int rightBoundary = endIndex;
       
        vector<int> temp;
        while ((left<=leftBoundary) && (right<=rightBoundary)){
            if (nums[leftBoundary] > nums[rightBoundary]){
                valMap[nums[leftBoundary]] = valMap[nums[leftBoundary]] +
                                    (rightBoundary - right + 1);
                temp.insert(temp.begin(),nums[leftBoundary] ) ;
                leftBoundary--;
            }else{
                temp.insert(temp.begin(),nums[rightBoundary] ) ;
                rightBoundary--;
            }
        }
        while (right <= rightBoundary){
            temp.insert(temp.begin(),nums[rightBoundary] ) ;
            rightBoundary--;
        }
        while (left<=leftBoundary){
            temp.insert(temp.begin(),nums[leftBoundary] ) ;
            leftBoundary--;
        }
       
        for (int i=0;i<=(endIndex-startIndex);i++){
            nums[i+startIndex] =  temp[i];
        }
     
    }
public:
   
    vector<int> countSmaller(vector<int>& nums) {
        for (int i=0;i<nums.size();i++){
          valMap[nums[i]] = 0;
        }
       
        vector<int> temp(nums);
        vector<int> elemGt;
        applyMerge(nums,0, nums.size()-1);
        for (int i=0;i<temp.size();i++){
            elemGt.push_back(valMap[temp[i]]);
        }
        return elemGt;  
    }
};