Find majority element - GFG practice solution

Given an array A of N elements. Find the majority element in the array. A majority element in an array A of size N is an element that appears more than N/2 times in the array.

 

Example 1:

Input:
N = 3 
A[] = {1,2,3} 
Output:
-1
Explanation:
Since, each element in 
{1,2,3} appears only once so there 
is no majority element.

Example 2:

Input:
N = 5 
A[] = {3,1,3,3,2} 
Output:
3
Explanation:
Since, 3 is present more
than N/2 times, so it is 
the majority element.

Your Task:
The task is to complete the function majorityElement() which returns the majority element in the array. If no majority exists, return -1.
 

Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
 

Constraints:
1 ≤ N ≤ 107

0 ≤ Ai ≤ 106

Practice Here :

Majority Element | Practice | GeeksforGeeks

Solution:

class Solution{

  public:

     // Function to find majority element in the array

    // a: input array

    // size: size of input array

    int majorityElement(int a[], int size)

    {

        

        // your code here

        int k =size/2;

        unordered_map<int,int> mp;

        for(int i=0;i<size;i++)

        {

            mp[a[i]]++; //store the count of all elements here in the map

        }

        

        for(auto it : mp)

        {

            if(it.second>k) //check whose count is greater than n/2

            return it.first;

        }

        return -1;

    }

};

Spirally traversing a matrix GFG Solution

Spirally traversing a matrix 

Medium 

---

Given a matrix of size r*c. Traverse the matrix in spiral form.

Example 1:

Input:
r = 4, c = 4
matrix[][] = {{1, 2, 3, 4},
           {5, 6, 7, 8},
           {9, 10, 11, 12},
           {13, 14, 15,16}}
Output: 
1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10
Explanation:

Example 2:

Input:
r = 3, c = 4  
matrix[][] = {{1, 2, 3, 4},
           {5, 6, 7, 8},
           {9, 10, 11, 12}}
Output: 
1 2 3 4 8 12 11 10 9 5 6 7
Explanation:
Applying same technique as shown above, 
output for the 2nd testcase will be 
1 2 3 4 8 12 11 10 9 5 6 7.

Your Task:
You dont need to read input or print anything. Complete the function spirallyTraverse() that takes matrix, r and c as input parameters and returns a list of integers denoting the spiral traversal of matrix. 

Expected Time Complexity: O(r*c)
Expected Auxiliary Space: O(r*c), for returning the answer only.

Constraints:
1 <= r, c <= 100
0 <= matrixi <= 100

Practice Here:

Spirally traversing a matrix | Practice | GeeksforGeeks

Solution :

class Solution

{   

    public: 

    //Function to return a list of integers denoting spiral traversal of matrix.

    vector<int> spirallyTraverse(vector<vector<int> > matrix, int r, int c) 

    {

        vector<int> v;

        int minRow =0;

        int maxRow = r-1;

        int maxCol = c-1;

        int minCol = 0;

        int i = minRow;

        int j = minCol;

        while(minRow<=maxRow||minCol<=maxCol){

            //cout<<i<<" j:"<<j<<endl;

            while((j<=maxCol&&j>=minCol)&&(i<=maxRow&&i>=minRow))

            v.push_back(matrix[i][j++]);

            minRow++;

            j--;

            i++;

         //cout<<i<<" j:"<<j<<endl;

            while((j<=maxCol&&j>=minCol)&&(i<=maxRow&&i>=minRow))

            v.push_back(matrix[i++][j]);

            maxCol--;

            j--;

            i--;

        //cout<<i<<" j:"<<j<<endl;

            while((j<=maxCol&&j>=minCol)&&(i<=maxRow&&i>=minRow))

                v.push_back(matrix[i][j--]);

                maxRow--;

            i--; 

            j++;

         //cout<<i<<" j:"<<j<<endl;

            while((j<=maxCol&&j>=minCol)&&(i<=maxRow&&i>=minRow))

              v.push_back(matrix[i--][j]);

              minCol++;

          j++;

          i++;

          

        }

        return v;

    }

};

Reverse a string using Stack GFG Solution

 Reverse a string using Stack 

Easy 

---

You are given a string S, the task is to reverse the string using stack.

 

Example 1:

Input: S="GeeksforGeeks"
Output: skeeGrofskeeG

 

Your Task:
You don't need to read input or print anything. Your task is to complete the function reverse() which takes the string S as an input parameter and returns the reversed string.

 

Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)

 

Constraints:
1 ≤ length of the string ≤ 100

Practice Here:

Parenthesis Checker | Practice | GeeksforGeeks

Solution:

class Solution

{

    public:

    //Function to check if brackets are balanced or not.

    bool ispar(string x)

    {

        // Your code here

        stack<char> st;

        for(char c: x)

        {

            if(c=='('||c=='{'||c=='[')

            st.push(c);

            else {

                if(st.empty())

                return false;

                if((c==')'&&st.top()=='(')||(c=='}'&&st.top()=='{')||(c==']'&&st.top()=='['))

                st.pop();

                else return false;

            }

        }

        

       return st.empty();

    }

};

Parenthesis Checker - Balance Parenthesis GFG problem

 Parenthesis Checker 

Easy

---

Given an expression string x. Examine whether the pairs and the orders of “{“,”}”,”(“,”)”,”[“,”]” are correct in exp.
For example, the function should return 'true' for exp = “[()]{}{[()()]()}” and 'false' for exp = “[(])”.

Example 1:

Input:
{([])}
Output: 
true
Explanation: 
{ ( [ ] ) }. Same colored brackets can form 
balaced pairs, with 0 number of 
unbalanced bracket.

Example 2:

Input: 
()
Output: 
true
Explanation: 
(). Same bracket can form balanced pairs, 
and here only 1 type of bracket is 
present and in balanced way.

Example 3:

Input: 
([]
Output: 
false
Explanation: 
([]. Here square bracket is balanced but 
the small bracket is not balanced and 
Hence , the output will be unbalanced.

Your Task:
This is a function problem. You only need to complete the function ispar() that takes a string as a parameter and returns a boolean value true if brackets are balanced else returns false. The printing is done automatically by the driver code.

Expected Time Complexity: O(|x|)
Expected Auixilliary Space: O(|x|)

Constraints:
1 ≤ |x| ≤ 32000

Note: The drive code prints "balanced" if function return true, otherwise it prints "not balanced".

Practice Here:

Parenthesis Checker | Practice | GeeksforGeeks

Solution:

class Solution

{

    public:

    //Function to check if brackets are balanced or not.

    bool ispar(string x)

    {

        // Your code here

        stack<char> st;

        for(char c: x)

        {

            if(c=='('||c=='{'||c=='[')

            st.push(c);

            else {

                if(st.empty())

                return false;

                if((c==')'&&st.top()=='(')||(c=='}'&&st.top()=='{')||(c==']'&&st.top()=='['))

                st.pop();

                else return false;

            }

        }

       return st.empty();

    }

};