//AMZN

Given a string s, rearrange the characters of s so that any two adjacent characters are not the same.

Return any possible rearrangement of s or return "" if not possible.


Example 1:

Input: s = "aab"
Output: "aba"
Example 2:

Input: s = "aaab"
Output: ""
 

Constraints:

1 <= s.length <= 500
s consists of lowercase English letters.

class Solution {
public:
string reorganizeString(string S) {
	vector<int> cnt(26);
	int mostFreq = 0, i = 0;

	for(char c : S)
		if(++cnt[c - 'a'] > cnt[mostFreq])
			mostFreq = (c - 'a');

	if(2 * cnt[mostFreq] - 1 > S.size()) return "";

	while(cnt[mostFreq]) {
		S[i] = ('a' + mostFreq);
		i += 2;
		cnt[mostFreq]--;
	}

	for(int j = 0; j < 26; j++) {
		while(cnt[j]) {
			if(i >= S.size()) i = 1;
			S[i] = ('a' + j);
			cnt[j]--;
			i += 2;
		}
	}

	return S;
}
};

// 2340. Minimum Adjacent Swaps to Make a Valid Array

class Solution {
public:
    int minimumSwaps(vector<int>& nums) {
        int minIdx = 0, maxIdx = 0;
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] < nums[minIdx]) {
                minIdx = i;
            }
            if (nums[i] >= nums[maxIdx]) {
                maxIdx = i;
            }
        }
        if (minIdx == 0 && maxIdx == nums.size() - 1) {
            return 0;
        }
        if (maxIdx < minIdx) {
            return (minIdx + (nums.size() - 1 - maxIdx) - 1);
        }
        return minIdx + (nums.size() - 1 - maxIdx);
    }
};

// You are given a non-negative integer array nums. In one operation, you must:

Choose a positive integer x such that x is less than or equal to the smallest non-zero element in nums.
Subtract x from every positive element in nums.
Return the minimum number of operations to make every element in nums equal to 0.

class Solution {
public:
    int minimumOperations(vector<int>& nums) {
        set<int> numsSet;
        
        for (auto e: nums) {
            if (e != 0)
                numsSet.insert(e);
        }
        return numsSet.size();
    }
};

// Maximum length subarray with positive sum
class Solution {
public:
    int getMaxLen(vector<int>& nums) {
        
        int n = nums.size();
        
        // pos_len will keep track of maximum length of subarray with positive product
        
        int pos_len = 0;
        
        // neg_len will track keep of maximum length of subarray with negative product
        
        int neg_len = 0;
        
        int maxi = 0;
        
        for(int i = 0; i < n; i++)
        {
            if(nums[i] == 0)
            {
                // now positive product and negative product both will be 0
                
                // so, pos_len and neg_len will be 0
                
                pos_len = 0;
               
                neg_len = 0;
            }
            else if(nums[i] > 0)
            {
                pos_len++;
                
                // if neg_len is zero it means negative product is 0, so starting with curr element will not lead to negative product, that's why it will remain 0
                
                // otherwise increment neg_len, b/c multiplying to neg_product with positive element will increment the length of neg_len
                
                if(neg_len != 0)
                {
                    neg_len++;
                }
            }
            else if(nums[i] < 0)
            {
                // here we will swap these (pos_len and neg_len)
                
                // store the neg_len
                
                int prev_neg_len = neg_len;
                
                // increment the neg_len
                
                neg_len = pos_len + 1;
                
                // if prev_neg_len is zero it means negative product is 0, so starting with curr element will not lead to positive product, that's why it will remain 0
                
                // otherwise update pos_len, b/c multiplying to neg_product with negative element will make it positive
                
                if(prev_neg_len == 0)
                {
                    pos_len = 0;
                }
                else
                {
                    pos_len = prev_neg_len + 1;
                }
            }
            
            // update maxi
            
            maxi = max(maxi, pos_len);
        }
        
        return maxi;
    }
};

// maximum subarray sum
class Solution {
public:
    int getMaxLen(vector<int>& nums) {
        vector<int> pos(nums.size(), 0);
        vector<int> neg(nums.size(), 0);
        int maxi = 0;
        int length = 0;
        int maxLength = 0;
        
        for (int i = 0; i < nums.size(); i++) {
            if (i == 0) {
                if (nums[i] > 0) {
                    pos[i] = nums[i];
                    length = 1;
                } else if (nums[i] < 0) {
                    neg[i] = nums[i];
                }
            } else {
                if (nums[i] == 0) {
                    pos[i] = neg[i] = 0;
                    length = 0;
                } else if (nums[i] < 0) {
                    pos[i] = neg[i-1] * nums[i];
                    neg[i] = pos[i-1] * nums[i];
                } else {
                    pos[i] = pos[i-1] * nums[i];
                    neg[i] = neg[i-1] * nums[i];
                }
            }
            if (maxi < pos[i]) {
                maxi = pos[i];
            }
        }
        return maxi;
    }
};

// Tic-Tac-Toe 
Assume the following rules are for the tic-tac-toe game on an n x n board between two players:

A move is guaranteed to be valid and is placed on an empty block.
Once a winning condition is reached, no more moves are allowed.
A player who succeeds in placing n of their marks in a horizontal, vertical, or diagonal row wins the game.
Implement the TicTacToe class:

TicTacToe(int n) Initializes the object the size of the board n.
int move(int row, int col, int player) Indicates that the player with id player plays at the cell (row, col) of the board. The move is guaranteed to be a valid move, and the two players alternate in making moves. Return
0 if there is no winner after the move,
1 if player 1 is the winner after the move, or
2 if player 2 is the winner after the move.

class TicTacToe {
public:
    TicTacToe(int n) {
        rows.resize(n), cols.resize(n);
        sz = n;
        diagnol = 0, antidiagnol = 0;
    }
    
    int move(int row, int col, int player) {
        if (player == 1) {
            rows[row]++;
            cols[col]++;
            if (row == col) {
                diagnol++;
            }
            if (row + col == sz - 1) {
                antidiagnol++;
            }
        } else {
            rows[row]--;
            cols[col]--;
            if (row == col) {
                diagnol--;
            }
            if (row + col == sz - 1) {
                antidiagnol--;
            }
        }
        if (abs(rows[row]) == sz || abs(cols[col]) == sz || abs(diagnol) == sz ||
           abs(antidiagnol) == sz) {
            return player;
        }
        return 0;
    }
    
    vector<int> rows, cols;
    int diagnol, antidiagnol;
    int sz;
};

// We are given an array asteroids of integers representing asteroids in a row.

For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed.

Find out the state of the asteroids after all collisions. If two asteroids meet, the smaller one will explode. If both are the same size, both will explode. Two asteroids moving in the same direction will never meet.


class Solution {
public:
    vector<int> asteroidCollision(vector<int>& asteroids) {
        stack<int> stk;
        vector<int> result;

        for (int i = 0; i < asteroids.size(); i++) {
            if (stk.empty() || asteroids[i] > 0) {
                stk.push(asteroids[i]);
            } else {
                if (stk.top() < 0) {
                    stk.push(asteroids[i]);
                    continue;
                } 
                if (stk.top() + asteroids[i] == 0) {
                    stk.pop();
                    continue;
                }
                if (abs(stk.top()) > abs(asteroids[i])) {
                    continue;
                }
                while (1) {
                    if (stk.top() + asteroids[i] == 0) {
                        stk.pop();
                        break;
                    }
                    if (stk.top() < 0) {
                        stk.push(asteroids[i]);
                        break;
                    }
                    if (abs(stk.top()) > abs(asteroids[i])) {
                        break;
                    }
                    stk.pop();
                    if (stk.empty()) {
                        stk.push(asteroids[i]);
                        break;
                    }
                }   
            }
        }
        while (!stk.empty()) {
            result.push_back(stk.top());
            stk.pop();
        }
        reverse(result.begin(), result.end());
        return result;
    }
};

// ZigZagLevelOrder

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if (!root) {
            return result;
        }
        bool reversal = false;
        queue<TreeNode *> q;
        q.push(root);
        int curLevel = 1, nextLevel = 0, trackLevel = 0;
        vector<int> curv;
        
        while (!q.empty()) {
            TreeNode *node = q.front();
            q.pop();
            curv.push_back(node->val);
            trackLevel++;
            if (node->left) {
                nextLevel++;
                q.push(node->left);
            }
            if (node->right) {
                nextLevel++;
                q.push(node->right);
            }
            if (trackLevel == curLevel) {
                curLevel = nextLevel;
                nextLevel = trackLevel = 0;
                if (reversal) {
                    reverse(curv.begin(), curv.end());
                }
                reversal = !reversal;
                result.push_back(curv);
                curv.clear();
            }
        }
        return result;
    }
};