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;
    }
};

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], val = 3

Your function should return length = 2, with the first two elements of nums being 2.

Solution:

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

Best Time to Buy and Sell Stock

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Example 1:

Input: [7, 1, 5, 3, 6, 4]
Output: 5

max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)

Solution:

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int profit = 0, min = INT_MAX;
        int size = prices.size();
        for (int i = 0; i < size; i++) {
            if (prices[i] < min) {
                min = prices[i];
            }
            profit = max(profit, prices[i] - min);
        }
        return profit;
    }
};

Linked List Cycle

Given a linked list, determine if it has a cycle in it.

Solution:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (head == NULL || head -> next == NULL)
            return false;
        ListNode *speedy = head;
        while (head != NULL && speedy != NULL) {
            head = head -> next;
            speedy = speedy -> next ? speedy -> next -> next : NULL;
            if (head == speedy)
                return true;
        }
        return false;
    }
};

Isomorphic Strings

Given two strings s and t, determine if they are isomorphic.

Two strings are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

For example,
Given "egg", "add", return true.

Given "foo", "bar", return false.

Given "paper", "title", return true.

Solution:

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        map<char, char> map, map2;
        int size = s.size(), size2 = t.size();
        if (size != size2)
            return false;
        for (int i = 0; i < size; i++) {
            if (map.find(s[i]) == map.end()) {
                map[s[i]] = t[i];
            } else if (map[s[i]] != t[i]) {
                return false;
            }
            if (map2.find(t[i]) == map2.end()) {
                map2[t[i]] = s[i];
            } else if (map2[t[i]] != s[i]) {
                return false;
            }
        }
        return true;
    }
};

Reverse Linked List

Reverse a singly linked list.

Solution:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        /*
        // Iterative.
        if (head == NULL)
            return head;
        ListNode *next = NULL, *pre = NULL, *curr = head;
        while (curr != NULL) {
            next = curr -> next;
            curr -> next = pre;
            pre = curr;
            curr = next;
        }
        return pre;
        */
        // Recursive.
        if (head == NULL || head -> next == NULL) {
            return head;
        }
        ListNode *end = NULL;
        end = reverseList(head -> next);
        head -> next -> next = head;
        head -> next = NULL;
        return end;
    }
};

Contains Duplicates III

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] andnums[j] is at most t and the difference between i and j is at most k.

Solution:

class Solution {
public:
    static int comp(pair<int, int> p1, pair<int, int> p2) {
        return p1.first < p2.first;
    }
    // Sliding window of t and search for index differnces.
    bool findAlmostDup(vector<pair<int, int> > pairs, int k, int t) {
        int size = pairs.size(), beg = 0, end = 1;
        while (beg < size && end < size) {
            if (abs(long(pairs[end].first) - long(pairs[beg].first)) <= t) {
                int i = beg;
                while (i < end) {
                    if (abs(pairs[end].second - pairs[i].second) <= k) {
                        return true;
                    } else {
                        i++;
                    }
                }
                end++;
            } else {
                beg++;
                if (beg == end) {
                    end++;
                }
            }
        }
        return false;
    }
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        int size = nums.size();
        if (size < 2)
            return false;
           
        //sort(nums.begin(), nums.end());
        vector<pair<int, int> > pairs;
        for (int i = 0; i < size; i++) {
            pairs.push_back(make_pair(nums[i], i));
        }
        sort(pairs.begin(), pairs.end(), comp);
        return findAlmostDup(pairs, k, t);
    }
};

Contains Duplicate II

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and j is at most k.

Solution:

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        map<int, int> map;
        int size = nums.size();
        if (size == 0)
            return false;
        for (int i = 0; i < size; i++) {
            if (map.find(nums[i]) == map.end()) {
                map[nums[i]] = i;
            } else {
                if (i - map[nums[i]] <= k) {
                    return true;
                } else {
                    map[nums[i]] = i;
                }
            }
        }
        return false;
    }
};

Contains Duplicate

Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

Solution:

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        int size = nums.size();
        if (size == 0)
            return false;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < size - 1; i++) {
            if (nums[i] == nums[i+1])
                return true;
        }
        return false;
    }
};


==== Or use any Map, Set etc to bookkeeping ===

Implement Stack using Queues

Implement the following operations of a stack using queues.

• push(x) -- Push element x onto stack.
• pop() -- Removes the element on top of the stack.
• top() -- Get the top element.
• empty() -- Return whether the stack is empty.

Notes:

• You must use only standard operations of a queue -- which means only push to back, peek/pop from front, size, and is empty operations are valid.
• Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
• You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).

Solution:

class Stack {
private:
    queue<int> que1;
    queue<int> que2;
    void transfer(queue<int>& q1, queue<int>& q2) {
        while (q1.size() != 1) {
                q2.push(q1.front());
                q1.pop();
        }
    }
public:
    // Push element x onto stack.
    void push(int x) {
        if (que2.empty()) {
            que1.push(x);
        } else {
            que2.push(x);
        }
    }

    // Removes the element on top of the stack.
    void pop() {
        if (que1.empty()) {
            transfer(que2, que1);
            que2.pop();
        } else {
            transfer(que1, que2);
            que1.pop();
        }
    }

    // Get the top element.
    int top() {
        int ret;
        if (que1.empty()) {
            transfer(que2, que1);
            ret = que2.front();
            que2.pop();
            que1.push(ret);
        } else {
            transfer(que1, que2);
            ret = que1.front();
            que1.pop();
            que2.push(ret);
        }
        return ret;
    }

    // Return whether the stack is empty.
    bool empty() {
        return que1.empty() && que2.empty();
    }
};



====== Another way Clean and nice =====

class Stack {
public:
    // Push element x onto stack.
    void push(int x) {
        queue<int> tmp;
        while (!q.empty()) {
            tmp.push(q.front());
            q.pop();
        }
        q.push(x);
        while (!tmp.empty()) {
            q.push(tmp.front());
            tmp.pop();
        }
    }

    // Removes the element on top of the stack.
    void pop() {
        q.pop();
    }

    // Get the top element.
    int top() {
        return q.front();
    }

    // Return whether the stack is empty.
    bool empty() {
        return q.empty();
    }
    
private:
    queue<int> q;
};