101. Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following [1,2,2,null,3,null,3] is not:

    1
   / \
  2   2
   \   \
   3    3

Approach : Use the simple recursive solution.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ bool checkIfSymmetric(struct TreeNode* n1, struct TreeNode* n2){ if(n1 == NULL && n2 == NULL) return true; if(n1 == NULL || n2 == NULL) return false; if(n1->val == n2->val){ return checkIfSymmetric(n1->left, n2->right) && checkIfSymmetric(n1->right, n2->left); } return false; } bool isSymmetric(struct TreeNode* root) { if(root == NULL){ return true; } return checkIfSymmetric(root->left, root->right); }

Read More

83. Remove Duplicates from Sorted List

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

Approach : The key to solve the problem is using the right loop condition and maintaining necessary pointers in each loop.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* deleteDuplicates(struct ListNode* head) { struct ListNode *cur, *_next; if(head == NULL || head->next == NULL){ return head; } cur = head; while(cur && cur->next){ //set the pointer of the current next to the next node if duplicate is found if(cur->val == cur->next->val){ _next = cur->next->next; free(cur->next); cur->next = _next; }else{ //else just move forward to next node cur = cur->next; } } return head; }

Read More

69. Sqrt(x)

Implement int sqrt(int x).

Return the floor if x is not a perfect square.

Approach :  Using binary search making sure that overflow does not happen by taking long long.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

class Solution { public: int mySqrt(int x) { if(x <= 1){ return x; } int low = 0, high = x / 2; //long to prevent overflow long long mid; while(low <= high){ mid = (low + high) / 2; //needs to be long to prevent overflow long long t = mid * mid; //second part is to return floor if x is not perfect square if( t == x || ((t < x) && ((mid + 1) * (mid + 1) > x))){ break; } else if(x < t){ high = mid - 1; }else{ low = mid + 1; } } return mid; } };

Here is the link to the ideone solution : http://ideone.com/taTCKu

Read More

67. Add Binary

Given two binary strings, return their sum (also a binary string).

For example,
a = "11"
b = "1"
Return "100"

Approach : The idea is to start from the right and keep adding digits and forwarding carry (if any). Also, take care of the case when one of them gets exhausted. For that, keep adding zero to the other one and forward carry if required. 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

string Solution::addBinary(string a, string b) { int lenA = a.length(), lenB = b.length(); int i = lenA - 1, j = lenB - 1; int carry = 0; stack<char> out; int sum = 0; while(i >= 0 || j >= 0){ if(i >= 0 && j >= 0){ //convert to int and add sum = a[i] - '0' + b[j] - '0' + carry; i--; j--; } else{ //string a is exhausted if(i < 0){ sum = b[j] - '0' + carry; j--; } //string b is exhausted else{ sum = a[i] - '0' + carry; i--; } } //setting the carry accordingly if(sum > 1){ carry = 1; }else{ carry = 0; } sum = sum % 2; //convert back to character char aChar = '0' + sum; out.push(aChar); } //for final carry if(carry){ out.push('1'); } string res = ""; //reverse the output while(!out.empty()){ res = res + out.top(); out.pop(); } return res; }

Here is the link to the ideone solution : http://ideone.com/o5r3Eq

Read More

14. Longest Common Prefix

Given an array of strings, the problem is to find out the longest common prefix of all the strings.

Return empty string if no common prefix exists.

Approach:
Use the brute force way approach to solve the problem. First find the shortest string (as the longest common prefix can be of at most this length), minLenStr, which takes O(n) time. Next, compare each string one by one with this minLenStr, and keep an variable which indicates the rightmost index of minLenStr, this loop takes O(mn) where m is the shortest length of all strings.

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string out = "";
        if(strs.size() == 0 ){
            return out;
        }
        //find the minimum length string since the longest common prefix can't be more than that length
        string minLenStr = strs[0];
        for(int i = 1; i < strs.size(); i++){
            if(strs[i].length() < minLenStr.length()){
                minLenStr = strs[i];
            }
        }
        //loop over all string and match all the starting characters, update the maximum size possible based on the starting matching characters
        int end = minLenStr.length();
        for(int i = 0; i < strs.size(); i++){
            int j = 0;
            while(j < end){
                if(minLenStr[j] != strs[i][j]){
                    break;
                }
                j++;
            }
            //update the maximum possible size
            if(j < end){
                end = j;
            }
        }
        return minLenStr.substr(0, end);
    }
};

Here is the link to the ideone solution : http://ideone.com/CWFcI8

Read More

53. Maximum Subarray

Write an efficient C program to find the sum of contiguous subarray within a one-dimensional array of numbers which has the largest sum.

Approach : Kadene's Algorithm

def max_subarray(A):
max_ending_here = max_so_far = 0
    for x in A:
        max_ending_here = max(0, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

Source: Wikipedia

Solution:

int maxSubArray(int* nums, int numsSize) {
    int curSum, maxSum = INT_MIN;
    curSum = 0;
    for(int i = 0; i < numsSize; i++){
        curSum = curSum + nums[i];
        if(curSum > maxSum){
            maxSum = curSum;
        }
        if(curSum < 0){
            curSum = 0;
        }
    }
    return maxSum;
}

Here is the link to the ideone solution : http://ideone.com/howey4

Read More

13. Roman to Integer

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

Approach:

According to an answer taken from here[1]:

• A number written in Arabic numerals can be broken into digits. For example, 1903 is composed of 1 (one thousand), 9 (nine hundreds), 0 (zero tens), and 3 (three units). To write the Roman numeral, each of the non-zero digits should be treated separately. In the above example, 1,000 = M, 900 = CM, and 3 = III. Therefore, 1903 = MCMIII.  
• The symbols "I", "X", "C", and "M" can be repeated three times in succession, but no more. (They may appear more than three times if they appear non-sequentially, such as XXXIX.) "V", "L", and "D" can never be repeated. 
• "I" can be subtracted from "V" and "X" only. "X" can be subtracted from "L" and "C" only. "C" can be subtracted from "D" and "M" only. "V", "L", and "D" can never be subtracted.
• Only one small-value symbol may be subtracted from any large-value symbol.

Here is the code for the same:

class Solution {
public:
    int romanToInt(string s) {
        map<char, int> m;
        m['I'] = 1;
        m['V'] = 5;
        m['X'] = 10;
        m['L'] = 50;
        m['C'] = 100;
        m['D'] = 500;
        m['M'] = 1000;
        int len = s.length();
        if(len <= 0)
            return 0;
        int result = m[s[len - 1]];
        for(int i = len - 2; i >= 0; i--){
            if(m[s[i]] < m[s[i+1]]){
                result = result - m[s[i]];
            }else{
                result = result + m[s[i]];
            }
        }
        return result;
    }
};

Here is the link to the ideone solution : http://ideone.com/CCO0w0

Read More

35. Search Insert Position

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.

[1,3,5,6], 5 → 2

[1,3,5,6], 2 → 1

[1,3,5,6], 7 → 4

[1,3,5,6], 0 → 0

Approach 1: Use modified binary search to get the required index

class Solution {
public:
    // recursive modified binary search
    int insertPos(vector<int> &nums, int low, int high, int target){
        //base case with 1 element
        if(low == high){
            if(nums[low] < target){
                return low + 1;
            }else{
                return low;
            }
        }
        //base case with 2 elements
        if(low == high - 1){
            if(nums[high] < target){
                return high + 1;
            }else if(target <= nums[low]){
                return low;
            }else{
                return high;
            }
        }
        //recursive call based on the index 
        int mid = low + ((high - low) >> 1);
        if(nums[mid] == target){
            return mid;
        }else if(nums[mid] < target && nums[mid + 1] > target){
            return mid + 1;
        }else if(nums[mid] > target){
            return insertPos(nums, low, mid - 1, target);
        }else{
            return insertPos(nums, mid + 1, high, target);
        }
    }
    
    int searchInsert(vector<int>& nums, int target) {
        return insertPos(nums, 0, nums.size()-1, target);
    }
};

Approach 2: Use lower_index() method supported by STL

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        vector<int>::iterator it = lower_bound(nums.begin(), nums.end(), target);
        return (it - nums.begin());
    }
};

Here is the link to the ideone solution : http://ideone.com/TbFRxX

Read More

66. Plus One

Given a non-negative integer represented as a non-empty array of digits, plus one to the integer. You may assume the integer do not contain any leading zero, except the number 0 itself. The digits are stored such that the most significant digit is at the head of the list.

Example:

If the vector has [1, 2, 3], the returned vector should be [1, 2, 4] as 123 + 1 = 124.

Approach:

1. Add 1 to the last digit
2. Forward the carry if exists and continue to the beginning

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

class Solution { public: vector<int> plusOne(vector<int>& digits) { int sum, carry = 0, n = digits.size(); //add 1 to the last digit sum = digits[n - 1] + 1; //see if there is a carry generated if(sum > 9){ carry = 1; digits[n - 1] = sum % 10; }else{ //if no carry, add 1 to lsb and return digits[n - 1] = sum; return digits; } //if carry, keep adding till there is no carry for(int i = n - 2; i >= 0; i--){ sum = digits[i] + carry; if(sum > 9){ carry = 1; digits[i] = sum % 10; }else{ //if no carry, return digits[i] = sum; return digits; } } //add 1 to the front if there is carry in the end if(carry){ digits.insert(digits.begin(), 1); } return digits; } };

Here is a link to the ideone solution : http://ideone.com/IbLgNA

Read More

26. Remove Duplicates from Sorted Array

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example,:

Given input array nums = [1,1,2], your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the new length.

Approach:

1. Copy the current element to the current index if it does not match to the previous element, else move to the next element and repeat the same for all elements of the array.

class Solution {
public:
    
    int removeDuplicates(vector<int>& nums) {
        int numsSize = nums.size();
        if(numsSize <= 1)
            return numsSize;
        
        int j = 1;
        for(int i = 1; i < numsSize; i++){
            if(nums[i] != nums[i - 1]){
                nums[j++] = nums[i];
                j++;
            }
        }
        return j;
    }
};

Here is the link to the ideone solution : http://ideone.com/T4iddh

Read More

58. Length of Last Word

Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string. If the last word does not exist, return 0.

Note: A word is defined as a character sequence consists of non-space characters only.

For example, for s = "Hello World", return 5.

Approach: The idea is to start traversing from the right (ignoring the right spaces if any) and continue till a space is not found. 

class Solution {
public:
    int lengthOfLastWord(string s) {
        int len = s.length();
        int i = len - 1, j = 0;
        while(s[i] == ' '){
            i--;
        }
        while(i >=0 && ((s[i] >= 'a' && s[i] <= 'z') || (s[i] >= 'A' && s[i] <= 'Z'))){
            i--;
            j++;
        }
        return j;
    }
};

Here is the link to the ideone solution : http://ideone.com/pYNIG9

Read More

27. Remove Element

Given an array and a value, remove all instances of that value in place and return the new length. Do not allocate extra space for another array, you must do this in place with constant memory.

The order of elements can be changed. It doesn't matter what you leave beyond the new length.

Example: Given input array nums = [3,2,2,3] and val = 3, your function should return length = 2, with the first two elements of nums being 2.

Approach: It is a very simple approach where we modify the array on the go by adding only those elements that do not match the target value. 

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int n = nums.size();
        int  j = 0;
        for(int i = 0; i < n; i++){
            if(nums[i] != val){
                nums[j++] = nums[i];
            }    
        }
        return j;
    }
};

Here is the link to the ideone solution : http://ideone.com/SqojbY

Read More

20 Valid Parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

Approach: The idea is to use Stack and implement the following algorithm:

1. if the current character is an opening bracket (of any type), push it to the stack and continue with the next character
2. else if the current character is a closing bracket, following cases apply:
1. if stack is empty - return error and exit
2. else if the current character and the stack top forms matching parenthesis i.e. opening and closing brackets are of same type, pop the stack top and continue with the next character otherwise return error and exit
3. Return error if the stack is not empty after all the characters are exhausted otherwise successful

class Solution {
public:
    
    int isMatching(stack<char> &stk, char c){
        if(stk.empty()){
            return 0;
        }
        char topC = stk.top();
        if( (topC == '(' && c == ')') || (topC == '{' && c == '}') || (topC == '[' && c == ']') )
            return 1;
        return 0;
    }
    
    bool isValid(string s) {
        stack<char> stk;
        int len = s.length();
        for(int i = 0; i < len; i++){
            if(s[i] == '(' || s[i] == '{' || s[i] == '['){
                    stk.push(s[i]);
                    continue;
            } else if((s[i] == ')' || s[i] == '}' || s[i] == ']') && isMatching(stk, s[i])){
                stk.pop();
                continue;
            }
            return false;
        }
        if(!stk.empty())
            return false;
        return true;
    }
};

Here is the link to the ideone solution : http://ideone.com/jzfJnv

Read More

Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* deleteDuplicates(ListNode* head) { if(head == NULL || head->next == NULL){ return head; } //create a dummy node to avoid the case of head value getting repeated which is difficult to handle struct ListNode *res = new struct ListNode(0); res->next = head; struct ListNode *cur = res; while(cur->next && cur->next->next){ //if the next value is same as its next value if(cur->next->val == cur->next->next->val){ int val = cur->next->val; //move forward if same value is repeating while(cur->next && cur->next->val == val){ cur->next = cur->next->next; } }else{ cur = cur->next; } } //return next of the dummy node return res->next; } };

Read More