Length of Array after removing consecutive balls
Given two arrays color[] and radius[] of length N each, where color[i] represents the color of the ith ball while radius[i] represents the radius of the ith ball. If two consecutive balls have the same color and size, both are removed from the array. The task is to find the length of the final array.
Examples:
Input: N = 3, color[] = {2, 2, 5}, radius[] = {3, 3, 4}
Output: 1
Explanation: First ball and second ball have the same color 2 and the same radius 3.So, after removing only one ball is left. It could not be removed from the array. Hence, the final array has length 1.Input: N = 4, color[] = {1, 3, 3, 1}, radius[] = {2, 5, 5, 2}
Output: 0
Explanation: Ball 2 and ball 3 have the same color 3 and the same radius5.So, they are removed. Now, we have got ourcolor[]={1, 1} and radius[]={2, 2}. Both the left balls are consecutive now and they are having same color and radius. So, these two balls are removed as well. Now, we are left with the empty final array. Hence, the length of the final array is 0.
Approach: This can be solved with the following idea:
This can be solved using a Stack data structure. If the top of the stack is equal to the next element remove and skip the element.
Below are the steps involved in the implementation of the code:
- We create a Pair class to store the color and radius together of the ith column.
- We declare a Stack<Pair> to store the color and radius in pair form.
- We run a loop from 0 to N and if the stack is empty, we push an ith column of color and radius together in the stack.
- If the stack is not empty, we check if the current ith element of color matches with the topmost element of the stack
(st.peek().a == color[i]) && ith element of radius matches with the topmost element of the stack (st.peek().b == radius[i]), we pop the particular pair. - Else we push it into the stack.
- At last, the pair left in the stack is the length of the final imaginary array, and we return the stack’s size().
Below is the implementation of the code:
C++
// C++ code to implement the above approach #include <bits/stdc++.h> using namespace std; // Structure struct pair1 { int a, b; pair1( int x, int y) { a = x; b = y; } }; // Function to find the length of // final Array int finLength( int N, int color[], int radius[]) { // code here stack<pair1> st; for ( int i = 0; i < N; i++) { if (st.empty()) { st.push(pair1(color[i], radius[i])); } else { // If adjacent balls have // same properties if (st.top().a == color[i] && st.top().b == radius[i]) { st.pop(); } else { st.push(pair1(color[i], radius[i])); } } } // Return the final size return st.size(); } // Driver code int main() { int N = 3; int color[] = { 2, 2, 5 }; int radius[] = { 3, 3, 4 }; // Function call cout << finLength(N, color, radius) << endl; return 0; } |
Java
// Java program to remove the balls import java.io.*; import java.util.*; // Structure class pair { int a, b; public pair( int a, int b) { this .a = a; this .b = b; } } class GFG { // Function to find the length of // final Array public static int finLength( int N, int [] color, int [] radius) { // code here Stack<pair> st = new Stack<>(); for ( int i = 0 ; i < N; i++) { if (st.isEmpty()) { st.push( new pair(color[i], radius[i])); } else { // If adjacent balls have // same properties if (st.peek().a == color[i] && st.peek().b == radius[i]) { st.pop(); } else { st.push( new pair(color[i], radius[i])); } } } // Return the final size return st.size(); } // Driver code public static void main(String[] args) { int N = 3 ; int color[] = { 2 , 2 , 5 }; int radius[] = { 3 , 3 , 4 }; // Function call System.out.println(finLength(N, color, radius)); } } |
Python3
# Structure class pair: def __init__( self , a, b): self .a = a self .b = b # Function to find the length of final Array def finLength(N, color, radius): # code here st = [] for i in range (N): if not st: st.append(pair(color[i], radius[i])) else : # If adjacent balls have same properties if st[ - 1 ].a = = color[i] and st[ - 1 ].b = = radius[i]: st.pop() else : st.append(pair(color[i], radius[i])) # Return the final size return len (st) # Driver code if __name__ = = '__main__' : N = 3 color = [ 2 , 2 , 5 ] radius = [ 3 , 3 , 4 ] # Function call print (finLength(N, color, radius)) #contributed by tushar rokade |
C#
// c# program to remove the balls using System; using System.Collections.Generic; // Structure class pair { public int a, b; public pair( int a, int b) { this .a = a; this .b = b; } } class GFG { // Function to find the length of final Array public static int FinLength( int N, int [] color, int [] radius) { // code here Stack<pair> st = new Stack<pair>(); for ( int i = 0; i < N; i++) { if (st.Count == 0) { st.Push( new pair(color[i], radius[i])); } else { // If adjacent balls have same properties if (st.Peek().a == color[i] && st.Peek().b == radius[i]) { st.Pop(); } else { st.Push( new pair(color[i], radius[i])); } } } // Return the final size return st.Count; } // Driver code public static void Main( string [] args) { int N = 3; int [] color = { 2, 2, 5 }; int [] radius = { 3, 3, 4 }; // Function call Console.WriteLine(FinLength(N, color, radius)); } } |
Javascript
// Structure class GFG { constructor(color, radius) { this .color = color; this .radius = radius; } } // Function to find the length of the // final Array function findFinalLength(N, colors, radii) { const stack = []; for (let i = 0; i < N; i++) { if (stack.length === 0) { stack.push( new GFG(colors[i], radii[i])); } else { // If adjacent balls have the // same properties if (stack[stack.length - 1].color === colors[i] && stack[stack.length - 1].radius === radii[i]) { stack.pop(); } else { stack.push( new Pair(colors[i], radii[i])); } } } // Return the final size return stack.length; } // Driver code function main() { const N = 3; const colors = [2, 2, 5]; const radii = [3, 3, 4]; // Function call console.log(findFinalLength(N, colors, radii)); } main(); |
1
Time Complexity: O(n), since we traverse once through the array.
Auxiliary Space: O(n), since we are using a Stack for storing the elements in pairwise form.
Contact Us