Search in Rotated Sorted Array

Problem:

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Solution:

class Solution {
public:
    int search(vector<int>& arr, int target) {
        int size = arr.size();
        int l = 0, r = size - 1, mid;
        while (l <= r) {
            mid = l + (r - l)/2;
            if (arr[mid] == target) {
                return mid;
            } else if (target < arr[mid]) {
                if (arr[mid] >= arr[l] &&
                    target < arr[l]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            } else {
                if (arr[mid] <= arr[r] &&
                    target > arr[r]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
        }
        return -1;
    }
};

Decode Ways

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.

Solution:

class Solution {
public:
    int numDecodings(string s) {
        vector<int> ans(s.size() + 1);
        if (s.size() == 0 || s[0] == '0') {
            return 0;
        }
        if (s.size() == 1)
            return 1;
        ans[0] = 1, ans[1] = 1;
        int tmp = s[0];
        for (int i = 2; i <= s.size(); i++) {
            if (s[i - 1] == '0') {
                if (s[i - 2] == '1' || s[i - 2] == '2') {
                    ans[i] = ans[i - 2];
                    continue;
                } else {
                    return 0;
                }
            }
            tmp = s[i - 2] - '0';
            if (tmp == 0) {
                // case: 101
                ans[i] = ans[i - 1];
                continue;
            }
            tmp = tmp * 10 + (s[i - 1] - '0');
            if (tmp > 26) {
                ans[i] = ans[i - 1];
            } else {  // case: 1 to 26: exception already included above i.e. 10 and 20.
                ans[i] = ans[i - 1] + ans[i - 2];
            }
        }
        return ans[s.size()];
    }

// ==== Recursive === not clean one ====
    /*int decod(string s, int l, int r) {
        if (s[l] == '0')
            return 0;
        if (r == 0)
            return r;
        if (r - l == 1) {
            if (s[r - 1] == '0')
                return 0;
            return 1;
        } else if (r - l == 2) {
            if ((s[l] == '1' || s[l] == '2') && s[l + 1] == '0') {
                return 1;
            } else if (s[l] == '1' ||
                       s[l] == '2' && s[l+1] <= '6' && s[l+1] >= '0') {
                return 2;
            } else if (s[l] == '0' || s[l + 1] == '0') {
                return 0;
            } else {
                return 1;
            }
        } else {
            if ((s[r - 2] == '1' || s[r - 2] == '2') && s[r - 1] == '0') {
                return decod(s, l, r - 2);
            } else if (s[r - 2] == '1' ||
                      (s[r - 2] == '2' && s[r - 1] <= '6' && s[r - 1] >= '0')) {
                return decod(s, l, r - 2) + decod(s, l, r - 1);
            } else if (s[r - 1] == '0' ||
                       (s[r - 2] == '0' && s[r-3] != '2' && s[r-3] != '1')) {
                return 0;
            } else {
                return decod(s, l, r - 1);
            }
        }
    }*/
};


============ Another attempt ======
==== Recursive and DP solutions (bottom-up, top-bottom)=======

class Solution {
public:
int numDecodings(string s) {
        // Recursive.
        // return helper(s, 0);
     
        // Dynamic programming (top bottom)
        //vector<int> dp(s.size() + 1, -1);
        //return helper_dynamic(s, 0, dp);
     
     
        // Bottom up DP. Give solution according to string length.
        vector<int> dp;
        dp.push_back(1);   // zero length string.
        if (s[0] == '0') {
            return 0;
        }
        dp.push_back(1);  // As first character is non zero.
     
        for (int i = 1; i < s.size(); i++) {
            int ans = 0;
            int cur_digit = (s[i] - '0');
            int prev_digit = (s[i - 1] - '0');
            if (cur_digit != 0) {
                ans = dp[i];         // last solution stored in dp.
            }
            int combined_digit = (prev_digit * 10) + cur_digit;
            if (combined_digit > 9 && combined_digit < 27) {
                ans += dp[i - 1];    // last to last solution stored in dp.
            }
         
          /* // Not needed by the way.
            if (ans == 0) {
                return 0;   // that means something like 100 occurred.
            }
         */
            dp.push_back(ans);    // dp[i + 1] = ans;    // can't do as vector element is not allocated.
        }
        return dp[s.size()];
    }





    /* //   Top Bottom Dynamic
    int helper_dynamic(string s, int start, vector<int>& dp) {
        // End of the array.
        if (start == s.size()) {
            return 1;
        }
        // First element 0.
        if (s[start] == '0') {
            return 0;
        }
        // Just one non zero element.
        if (s.size() - start == 1) {
            return 1;
        }
        int ans;
        if (dp[start + 1] != -1) {
            ans = dp[start + 1];
        } else {
            ans = helper_dynamic(s, start + 1, dp);
            dp[start + 1] = ans;
        }

        int num = (s[start] - '0') * 10 + (s[start + 1] - '0');
        if (num > 9 && num <= 26) {
            if (dp[start + 2] != -1) {
                ans += dp[start + 2];
            } else {
                ans += helper_dynamic(s, start + 2, dp);
                dp[start + 2] = ans;
            }
        }
     
        return ans;
    }
    */
 
// Recursive.
    /*
        ans = {s[0].decode(s[1..n]) + s[0,1].decode(s[2..n])}
        i.e. ans = (first element & remaining sols) +
                    (first two element & remaining sols)
    */
    /*
    int helper(string s, int start) {
        // End of the array.
        if (start == s.size()) {
            return 1;
        }
        // First element 0.
        if (s[start] == '0') {
            return 0;
        }
        // Just one non zero element.
        if (s.size() - start == 1) {
            return 1;
        }
     
        int ans = helper(s, start + 1);
        int num = (s[start] - '0') * 10 + (s[start + 1] - '0');
        if (num > 9 && num <= 26) {
            ans += helper(s, start + 2);
        }
     
        return ans;
    }
    */
};

===================== Another attempt ======
int numDecodings(string s) { if (s.size() == 0 || s[0] == '0') { return 0; } vector<int> dp(s.size() + 1, 0); dp[0] = 1; dp[1] = 1; for (int i = 1; i < s.size(); i++) { if (s[i] != '0') { dp[i + 1] += dp[i]; } int val = (s[i - 1] - '0') * 10 + (s[i] - '0'); if (val >= 10 && val <= 26) { dp[i + 1] += dp[i - 1]; } if (val == 0) { return 0; } } return dp[s.size()]; }

Count Primes

Count the number of prime numbers less than a non-negative number, n.

Hint:

1. Let's start with a isPrime function. To determine if a number is prime, we need to check if it is not divisible by any number less than n. The runtime complexity of isPrimefunction would be O(n) and hence counting the total prime numbers up to n would be O(n2). Could we do better?
2. As we know the number must not be divisible by any number > n / 2, we can immediately cut the total iterations half by dividing only up to n / 2. Could we still do better?
3. Let's write down all of 12's factors:

   2 × 6 = 12
   3 × 4 = 12
   4 × 3 = 12
   6 × 2 = 12
   

   As you can see, calculations of 4 × 3 and 6 × 2 are not necessary. Therefore, we only need to consider factors up to √n because, if n is divisible by some number p, then n = p ×q and since p ≤ q, we could derive that p ≤ √n.
   Our total runtime has now improved to O(n1.5), which is slightly better. Is there a faster approach?

   public int countPrimes(int n) {
      int count = 0;
      for (int i = 1; i < n; i++) {
         if (isPrime(i)) count++;
      }
      return count;
   }
   
   private boolean isPrime(int num) {
      if (num <= 1) return false;
      // Loop's ending condition is i * i <= num instead of i <= sqrt(num)
      // to avoid repeatedly calling an expensive function sqrt().
      for (int i = 2; i * i <= num; i++) {
         if (num % i == 0) return false;
      }
      return true;
   }
   

4. The Sieve of Eratosthenes is one of the most efficient ways to find all prime numbers up to n. But don't let that name scare you, I promise that the concept is surprisingly simple.
   
   Sieve of Eratosthenes: algorithm steps for primes below 121. "Sieve of Eratosthenes Animation" by SKopp is licensed under CC BY 2.0.
   We start off with a table of n numbers. Let's look at the first number, 2. We know all multiples of 2 must not be primes, so we mark them off as non-primes. Then we look at the next number, 3. Similarly, all multiples of 3 such as 3 × 2 = 6, 3 × 3 = 9, ... must not be primes, so we mark them off as well. Now we look at the next number, 4, which was already marked off. What does this tell you? Should you mark off all multiples of 4 as well?
5. 4 is not a prime because it is divisible by 2, which means all multiples of 4 must also be divisible by 2 and were already marked off. So we can skip 4 immediately and go to the next number, 5. Now, all multiples of 5 such as 5 × 2 = 10, 5 × 3 = 15, 5 × 4 = 20, 5 × 5 = 25, ... can be marked off. There is a slight optimization here, we do not need to start from 5 × 2 = 10. Where should we start marking off?
6. In fact, we can mark off multiples of 5 starting at 5 × 5 = 25, because 5 × 2 = 10 was already marked off by multiple of 2, similarly 5 × 3 = 15 was already marked off by multiple of 3. Therefore, if the current number is p, we can always mark off multiples of p starting at p2, then in increments of p: p2 + p, p2 + 2p, ... Now what should be the terminating loop condition?
7. It is easy to say that the terminating loop condition is p < n, which is certainly correct but not efficient. Do you still remember Hint #3?
8. Yes, the terminating loop condition can be p < √n, as all non-primes ≥ √n must have already been marked off. When the loop terminates, all the numbers in the table that are non-marked are prime.
   The Sieve of Eratosthenes uses an extra O(n) memory and its runtime complexity is O(n log log n). For the more mathematically inclined readers, you can read more about its algorithm complexity on Wikipedia.

   public int countPrimes(int n) {
      boolean[] isPrime = new boolean[n];
      for (int i = 2; i < n; i++) {
         isPrime[i] = true;
      }
      // Loop's ending condition is i * i < n instead of i < sqrt(n)
      // to avoid repeatedly calling an expensive function sqrt().
      for (int i = 2; i * i < n; i++) {
         if (!isPrime[i]) continue;
         for (int j = i * i; j < n; j += i) {
            isPrime[j] = false;
         }
      }
      int count = 0;
      for (int i = 2; i < n; i++) {
         if (isPrime[i]) count++;
      }
      return count;
   }

Solution:

class Solution {
public:
    int countPrimes(int n) {
        int ans = 0, idx = 0;
        vector<bool> num(n + 1, true);
        if (n < 2)
            return ans;
        num[0] = false; num[1] = false;
        for (int i = 2; i <= n; i++) {
            if (num[i] == true) {
                ans++;
                idx = i;
                while (idx <= n) {
                    num[idx] = false;
                    idx += idx;
                }
            }
        }
        return ans;
    }
};

==== More optimized Solution already given above. ====

Valid Sudoku

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

A partially filled sudoku which is valid.

Note:
A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.

Solution:

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        map<char, bool> map, map2, map3;
        int size = board.size();
        // Check Rows and cols.
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if ((board[i][j] != '.' && map.find(board[i][j]) != map.end()) ||
                    (board[j][i] != '.' && map2.find(board[j][i]) != map2.end())) {
                    return false;
                } else {
                    map[board[i][j]] = true;
                    map2[board[j][i]] = true;
                }
            }
            map.clear();
            map2.clear();
        }
        // Box check.
        for (int i = 0; i < 9; i=i+3) {
            for (int j = 0; j < 9; j=j+3) {
                for (int ii = i; ii < i + 3; ii++) {
                    for (int jj = j; jj < j + 3; jj++) {
                        if (board[ii][jj] != '.' && map3.find(board[ii][jj]) != map3.end()) {
                            return false;
                        } else {
                            map3[board[ii][jj]] = true;
                        }
                    }
                }
                map3.clear();
            }
        }
        return true;
    }
};

====================== Again ===============
class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        if (board.size() != 9 || board[0].size() != 9) {
            return false;
        }
        if (!rowValid(board) || !colValid(board) || !boxValid(board)) {
            return false;
        }
        return true;
    }
   
    bool rowValid(vector<vector<char>>& board) {
        for (auto row : board) {
            set<int> st;
            for (char ch : row) {
                if (ch != '.') {
                    if (st.count(ch)) {
                        return false;
                    }
                    st.insert(ch);
                }
            }
        }
        return true;
    }
   
    bool colValid(vector<vector<char>>& board) {
        for (int i = 0; i < 9; i++) {
            set<int> st;
            for (int j = 0; j < 9; j++) {
                if (board[j][i] != '.') {
                    if (st.count(board[j][i])) {
                        return false;
                    }
                    st.insert(board[j][i]);
                }
            }
        }
        return true;
    }
   
    bool boxValid(vector<vector<char>>& board) {
        for (int ii = 0; ii < 9; ii = ii + 3) {
            for (int jj = 0; jj < 9; jj = jj + 3) {
                set<int> st;
                for (int i = 0; i < 3; i++) {
                    for (int j = 0; j < 3; j++) {
                        if (board[ii + i][ jj + j] != '.') {
                            if (st.count(board[ii + i][ jj + j])) {
                                return false;
                            }
                            st.insert(board[ii + i][ jj + j]);
                         }
                    }
                }
            }
        }
        return true;
    }
};

============= Single iteration solution ===========

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        unordered_set<string> st;
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] == '.') continue;
                string t = "(" + to_string(board[i][j]) + ")";
                string row = to_string(i) + t, col = t + to_string(j), cell = to_string(i / 3) + t + to_string(j / 3);
                if (st.count(row) || st.count(col) || st.count(cell)) return false;
                st.insert(row);
                st.insert(col);
                st.insert(cell);
            }
        }
        return true;
    }
};

ZigZag Conversion

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

Solution:

class Solution {
public:
    string convert(string s, int numRows) {
        vector<string> ans(numRows);
        string sol;
        if (s.empty() || numRows == 1)
            return s;
        // metadata for number of vector<string>
        bool flag = false;
        int j = 0;
           
        int size = s.size();
        for (int i = 0; i < size; i++) {
            if (flag == false) {
                ans[j++].push_back(s[i]);
                flag = (j == numRows ? true : false);
                if (flag == true)
                    j--;
            } else {
                ans[--j].push_back(s[i]);
                flag = (j == 0 ? false : true);
                if (flag == false)
                    j++;
            }
        }
       
        for (int i = 0; i < numRows; i++) {
            sol += ans[i];
        }
        return sol;
    }
};

Roman To Integer

Given a roman numeral, convert it to an integer.

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

Solution:
class Solution {
public:
    int romanToInt(string s) {
        int num = 0;
        int size = s.size();
        if (size == 0)
            return num;
        // Initialize.
        map<char, int> map;
        map['I'] = 1;
        map['V'] = 5;
        map['X'] = 10;
        map['L'] = 50;
        map['C'] = 100;
        map['D'] = 500;
        map['M'] = 1000;

        num = map[s[size - 1]];
        for (int i = size - 2; i >= 0; i--) {
            if (map[s[i + 1]] > map[s[i]])
                num -= map[s[i]];
            else
                num += map[s[i]];
        }
        return num;
    }
};

=============

class Solution {

public:

    int romanToInt(string s) {

        map<char, int> mp = {{'I', 1}, {'V', 5}, {'X', 10}, {'L', 50}, {'C', 100}, {'D', 500}, {'M', 1000}};

        int ans = 0;

        

        if (s.size() == 0) {

            return ans;

        } else if (s.size() == 1) {

            return mp[s[0]];

        }

        

        int back = -1, cur = 0;

        while (cur < s.size()) {

            ans += mp[s[cur]];

            if (back != -1 && mp[s[back]] < mp[s[cur]]) {

                ans -= (2 * mp[s[back]]);

            }

            back = cur;

            cur++;

        }

        return ans;

    }

};

Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Solution:
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *head = NULL, *trav = NULL;
        while (l1 != NULL && l2 != NULL) {
            if (l1 -> val < l2 -> val) {
                if (trav == NULL) {
                    trav = l1;
                    head = l1;
                } else {
                    trav -> next = l1;
                    trav = l1;
                }
                l1 = l1 -> next;
            } else {
                if (trav == NULL) {
                    trav = l2;
                    head = l2;
                } else {
                    trav -> next = l2;
                    trav = l2;
                }
                l2 = l2 -> next;
            }
        }
        if (trav != NULL)
            trav -> next = (l1 != NULL ? l1 : l2);
        else
            head = (l1 != NULL ? l1 : l2);
        return head;
    }
};