Binary Tree PreOrder Traversal

Given a binary tree, return the preorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,2,3].

Note: Recursive solution is trivial, could you do it iteratively?

Solution : 


CODE:
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector preorderTraversal(TreeNode *root) {
      
       vector result;
       stack s;
       if(root!=NULL)
       s.push(root);
       while(!s.empty()){
           TreeNode *curr = s.top();
           result.push_back(curr->val);
           s.pop();
           if(curr->right)
           s.push(curr->right);
           if(curr->left)
           s.push(curr->left);
       }
       return result;
    }
};

Single Number II

Given an array of integers, every element appears three times except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Solution : 

Came across a beautiful solution in the official LeetCode's Discuss section.

Unfortunately no explanation was offered, hence will try to explain it here.

As in the case of the Single Number question, we need to manipulate the bits of the numbers in the array.

For eg : A = [ 2, 3, 3, 3]

We count the number of 1s for each bit position. Then find mod 3 of each of them. The bit positions having mod 3  equal to one are the bits that are set due to the number occurring once.

Writing the Binary Representation of the numbers.

                                                                  0 0 1 0

                                                                  0 0 1 1

                                                                  0 0 1 1

                                                                  0 0 1 1

                                                            ----------------

We count the number of 1s for each bit ->  0 0 4 3

Taking modulo 3 we get                             0 0 1 0

and that's our answer. -> 2

Here's the code : 

The code basically has 2 variables  one & two. 

one is used to  mark bits that have mod 3 = 1.

two is used to mark bits that have mod 3 = 2.

Hope that helped!

Single Number

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Solution : 

Rule of thumb :  XORing a number with itself results in 0. 

eg: A = [2, 3, 3, 1, 1]

if we XOR the numbers we will be left with the number that only occurred once.

0010 ^ 0011 ^ 0011 ^ 0001 ^ 0001  = 0010 = 2.

Code : 

class Solution {
public:
    int singleNumber(int A[], int n) {
       int c = A[0] ;
       for(int i=1;i
           c=c^A[i];
       }
       return c;
    }

};

Hope that helped!

Jump Game

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

Solution : 

Remove Nth Node From End of List

Given a linked list, remove the n^th node from the end of list and return its head.
For example,

   Given linked list: 1->2->3->4->5, and n = 2.

   After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:
Given n will always be valid.
Try to do this in one pass.

Solution:

class Solution {
public:
    ListNode *removeNthFromEnd(ListNode *head, int n) {

       ListNode  *fast , *slow;
       fast=slow=head;
       for(int i=0; inext;
       if (fast==NULL) return head->next;
       else{
           while(fast->next!=NULL){
               fast=fast->next;
               slow=slow->next;
           }
           slow->next=slow->next->next;
       }
       return head;
    }
};

Not much to explain here.

Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

This is the simple solution.
  
class Solution {
public:
    string longestCommonPrefix(vector &strs) {
 
         if(strs.size() == 0) return "";

        int num = strs.size();
        int len = strs[0].size();

        for(int j = 0; j            for(int i = 1; i                 if(strs[i][j]!=strs[i-1][j]){
                    return strs[0].substr(0,j);
                }
            }
        }
        return strs[0];    
    }
};

We have a string vector containing different strings. We start off with first letter of string (j=0).
 The other loop starts at i=1 pointing to the string at index 1 in the vector.
The outer loop is for iterating through particular j for all the strings.
In the first iteration of the inner loop i=1, j=0;
strs[1][0] refers to first character of the string at index 1.
strs[0][0] refers to the first character of the string at index 0.
Both of them are compared. If found unequal we return the substring strs[0].substr(0,0) which basically is null here.
In the second iteration of the inner loop i=2, j=0;
strs[2][0] (first character of the string at index 2) is compared with strs[1][0] (first character of string at index 1). Similarly we iterate through all the strings (i) comparing their first characters with the first character of the previous string (i-1).
Then the outer loop is incremented (we compare all strings for their second characters) and proceed so on.
In the worst case the complexity will be O(n².

Integer to Roman

Given an integer, convert it to a roman numeral.
Input is guaranteed to be within the range from 1 to 3999.

Solution:
We take two arrays containing the special cases. Since the number will not be greater than 3999, we need to know the Roman representations of up to he number 1000.
M = 1000
D = 500
C = 100
L = 50
X = 10
V = 5
I = 1

Here's the code. I got it from the comments on the Leetcode's problem page. Concise and precise.

class Solution {
public:
    string intToRoman(int num) {
        string result;
        int newnum;
        int values[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        string symbols[] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        for(int i =0; i<13;i++)
        {
            newnum = num/values[i];
             num = num-newnum*values[i];
            while(newnum--)
            {
                result.append(symbols[i]);
            }
      
        }
        return result;
    }
};

Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
"((()))", "(()())", "(())()", "()(())", "()()()"

This is a classic problem involving Catalan numbers.
Catalan numbers is calculated using 

Catalann = (1/n+1)2nCn

There are many counting problems in combinatorics whose solution is given by the Catalan numbers.

• C_n is the number of Dyck words of length 2n. A Dyck word is a string consisting of n X's and n Y's such that no initial segment of the string has more Y's than X's . For example, the following are the Dyck words of length 6:

        XXXYYY     XYXXYY     XYXYXY     XXYYXY     XXYXYY.

• Re-interpreting the symbol X as an open parenthesis and Y as a close parenthesis, C_n counts the number of expressions containing n pairs of parentheses which are correctly matched:

         ((()))     ()(())     ()()()     (())()     (()())

 

In our case for n =3, we get 5 combinations as can be calculated.

 

We solve this problem using recursion. The basic idea is we keep 2 stocks of parentheses. Open and  Close. 

The combinations are made by picking parentheses from these stocks. When both these stocks are empty, we end up with one particular combination. We store it in our string vector and the recursion lets us find other combinations. Here's the code for it : 

  

class Solution {
public:
    vector generateParenthesis(int n) {

      vector ans;
      if (n>0) brackets(ans, "", n, 0);
      return ans;  

    }

    void brackets(vector & ans, string s, int openStock,  int closeStock) {
    if (openStock==0 && closeStock==0) ans.push_back(s);
 
   if(openStock>0) brackets(ans, s+"(", openStock-1, closeStock+1);
   if(closeStock>0) brackets(ans, s+")", openStock, closeStock-1);
}
};  

To understand, try dry run for n =2. It will help you understand better. 

Palindrome number

Determine whether an integer is a palindrome. Do this without extra space. 
Solution : 
Code:

class Solution {

public:

    bool isPalindrome(int x) {

        if(x<0) return false;

    int div = 1;

    while(x/div>=10)

    {

        div=div*10;

    }

    while(x!=0)

    {

        int l = x/div;

        int r = x%10;

        if(l!=r) return false;

        x = (x%div)/10;

        div/=100;

    }

    return true;

    }   

};

String to Integer (atoi)

Implement atoi to convert a string to an integer.
Solution : 
Code:

class Solution {

public:

    int atoi(const char *str) {

      

       if (*str =='\0') return 0;

       // skip whitespaces.

       while ((*str) == ' ') str++;

       // sign

       int sign = 1;

       if(*str == '-')

       {

            sign = -1;

            str++;

       }

       else if(*str == '+')

       {

           sign = 1;

           str++;

       }

       // convert to number

       int num = 0;

       while (isdigit(*str))

       {

            if(((num == 214748364) && ((*str) - '0' >7)) || (num > 214748364))

            return (sign>0? INT_MAX : INT_MIN);

            num = num*10 + ((*str)-'0');

            str++;

       }

       return (sign*num);

    }

};

Regular Expression Matching

Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character. 
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:

 bool isMatch(const char *s, const char *p)

Some examples:

isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

A good explanation from the official leetcode site can be found here

It is somewhat easy to think of an algorithm for most of the cases except for patterns which have a .* .
For eg :
s = "abcbcd" ; p ="a.*c.*cd"
Here, ".*" in p means repeat '.' 0 or more times. 
Since '.' can match any character, it is not clear how many times '.' should be repeated. Should the 'c' in p matches the first or second 'c' in s? Unfortunately, there is no way to tell without using some kind of exhaustive search.
Here is the algorithm presented by leetcode. It's short but do devote ample time going through it, lest you overlook some test cases. 

Code:
    bool isMatch(const char *s, const char *p) {  
            assert(s && p);
    if (*p == '\0') return *s == '\0';

    // next char is not '*': must match current character
    if (*(p+1) != '*') {
        assert(*p != '*');
        return ((*p == *s) || (*p == '.' && *s != '\0')) && isMatch(s+1, p+1);
    }
    // next char is '*'
    while ((*p == *s) || (*p == '.' && *s != '\0')) {
        if (isMatch(s, p+2)) return true;
        s++;
    }
    return isMatch(s, p+2);
    }

Longest Palindromic Substring

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

Solution:
1. Brute Force. Takes O(n^3).
2. Look here for the Leetcode explanation which uses DP. Time and space complexity O(n^2).
    There is also a O(n) solution which we shall see in a later post.

Code:
(same as in the link)

class Solution {
public:
    string longestPalindrome(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
       bool flag[1000][1000] = {false};
       int n=s.length();
       int longestBegin = 0;
       int maxlen = 1;
       int i,j;
       for(i=0; i<n; i++)
       {
           flag[i][i] = true;
       }
       for(i=0; i<n-1; i++)
       {
           if (s[i]==s[i+1])
           {
               flag[i][i+1]= true;
               longestBegin = i;
               maxlen = 2;
           }
       }
       for(int len = 3; len <= n; len++)
       for(i=0; i<n-len+1;i++)
       {
           j=i+len-1;
           if(s[i]==s[j] && flag[i+1][j-1]==true)
           {
               flag[i][j]=true;
               longestBegin = i;
               maxlen = len;
           }
       }
       return s.substr(longestBegin,maxlen);
    }
};

Add Two Numbers

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

Solution:

A rather easy question. We'll just have to keep in mind the carry at the end of either or both of the linked lists given.

Code:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
      ListNode *p1 =l1;
      ListNode *p2 =l2;
      ListNode *head = NULL;
      ListNode *temp = NULL;
      ListNode *tail = NULL;
      int sum =0;
      int carry =0;
      while(p1 && p2)
      {
         sum = carry+p1->val+p2->val;
         carry = sum/10;
         sum = sum%10;
         temp = new ListNode(sum);
         if(head==NULL) {head = temp; tail = temp;}
         else
         {tail->next = temp; tail = temp;}
         p1=p1->next;
         p2=p2->next;
      }
      while(p1)
      {
          sum = carry+p1->val;
          carry = sum/10;
          sum = sum%10;
          temp = new ListNode(sum);
          tail->next= temp;
          tail = temp;
          p1=p1->next;
      }
      while(p2)
      {
         sum = carry+p2->val;
          carry = sum/10;
          sum = sum%10;
          temp = new ListNode(sum);
          tail->next= temp;
          tail = temp;
          p2=p2->next;
      }
      if(carry)
      {
          temp = new ListNode(carry);
          tail->next= temp;
          tail = temp; 
      }
        return head;
    }
 
};

Two Sum

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

There are 2 ways to solve this in better than O(n^2)
1. Sort the given array. Take 2 pointers, one at the start, other at the end. 
if their sum exceeds the target, decrement the end pointer. If their sum is less than the target increment the start pointer.Do this until you find a pair.
Takes no extra space. Time Complexity O(nlogn).

2. The other approach is to use map. Map the elements of the array. Take the elements one by one, subtract it from the target and search for the (target-element) part in the map.
Time and Space Complexity O(n).

Code :

class Solution {
public:
    vector<int> twoSum(vector<int> &numbers, int target) {
        vector<int> result;
        map<int, int> mymap;
        int i;
        int toSearch;
        for(  i=0; i<numbers.size();++i)
        mymap[numbers[i]]= i;
        for(i=0; i<numbers.size(); ++i)
        {
            toSearch = target-numbers[i];
            if(mymap.find(toSearch)!=mymap.end())
            {
                result.push_back(i+1);
                result.push_back(mymap[toSearch]+1);
            }
        }
    return result;
    }
};