ms1797

/*
  Infix to postfix conversion in C++
  Input Postfix expression must be in a desired format.
  Operands and operator, both must be single character.
  Only '+'  ,  '-'  , '*', '/' and '^' (for exponentiation)  operators are expected.
*/
#include<iostream>
#include<stack>
#include<string>

ms1797

/*Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, 
find the area of largest rectangle in the histogram.

Largest Rectangle in Histogram: Example 1

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

Largest Rectangle in Histogram: Example 2

The largest rectangle is shown in the shaded area, which has area = 10 unit.

ms1797

/*Problem Statement::MAXPPROD_INTERVIEWBIT

You are given an array A containing N integers. The special product of each ith integer in this array is 
defined as the product of the following:<ul>

LeftSpecialValue: For an index i, it is defined as the index j such that A[j]>A[i] (i>j). 
If multiple A[j]’s are present in multiple positions, the LeftSpecialValue is the maximum value of j. 

RightSpecialValue: For an index i, it is defined as the index j such that A[j]>A[i] (j>i). 
If multiple A[j]s are present in multiple positions, the RightSpecialValue is the minimum value of j.

ms1797

#include <bits/stdc++.h>
using namespace std;

/**
 * Given nxn board place n queen on this board so that they dont attack each other. One solution is to find
 * any placement of queens which do not attack each other. Other solution is to find all placements of queen
 * on the board.
 *
 * Time complexity O(n^n)
 * Space complexity O(n*n)

ms1797

/*
Given a collection of numbers, return all possible permutations.

Example:

[1,2,3] will have the following permutations:

[1,2,3]
[1,3,2]
[2,1,3] 

ms1797

/*
Permutation II ::

Problem Statement:: 
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
(https://leetcode.com/problems/permutations-ii/)

Example:

Input: [1,1,2]

ms1797

/*
The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. 
A gray code sequence must begin with 0.

Example 1:

Input: 2
Output: [0,1,3,2]

ms1797

/*
Largest Continuous Sequence Zero Sum :
(https://www.interviewbit.com/problems/largest-continuous-sequence-zero-sum/)
Find the largest continuous sequence in a array which sums to zero.

Example:
Input:  {1 ,2 ,-2 ,4 ,-4}
Output: {2 ,-2 ,4 ,-4}

Input: arr[] = {15, -2, 2, -8, 1, 7, 10, 23};

ms1797

vector<vector<int> > Solution::fourSum(vector<int> &A, int B) {
    int N = A.size();
   //mapping sum value to a vector of pair indices
    unordered_map<int, vector<pair<int, int> > > Hash;
    vector<vector<int> >Ans;
 
    for(int i = 0; i < N; ++i) {
        for(int j = i + 1; j < N; ++j) {
            //calculate sum with i and j indices
            int Sum = A[i] + A[j];

ms1797

class Solution {
public:    
    string minWindow(string s, string t) {
        unordered_map<char, int> table;
        
        // initialize frequency table for t
        for(char c : t){
            table[c]++;
        }