Scaler Topics Fortnightly Contest - 25 Editorial
FREE
DSA Fortnightly - 25 Editorial
This article is part of the Scaler Topics Fortnightly Contest - 25
Tile Square Problem
Jack, a skilled craftsman, faces the task of adorning a rectangular wall measuring N units in length and M units in width. This wall is segmented into a grid of N * M individual blocks, each measuring 1 unit by 1 unit. His goal is to embellish the wall by affixing colorful tiles onto it, arranging them to create a single square pattern. The challenge lies in determining the minimum number of additional tiles required to form this square, considering that some tiles have already been placed on the wall and cannot be removed.
Provided with an array of strings A of size N, where each A[i] represents the i-th row of the wall and A[i][j] represents the j-th block in the i-th row, the letter 'E' denotes an empty block (indicating no tile placed), while 'T' signifies a tile already present on the wall. Calculate the minimum number of new tiles needed to construct a square on the wall. If it's impossible to form a square pattern with the existing tiles, return -1.
Problem Constraints
Input Format
- The first and only argument is an array of strings A.
Output Format
- Return an integer denoting the required answer.
Build an AI-First Career, Master the Complete Skillset
Choose from our industry-leading programs designed for career success
Modern Software and AI Engineering Program
Master full-stack development with AI integration
+1000 moreModern Data Science and ML with specialisation in AI
Advanced data science techniques with AI specialization
+1000 moreAdvanced AIML with Specialisation in Agentic AI
Deep dive into AIML with focus on Agentic systems
+1000 moreDevOps, Cloud & AI Platform Engineering
Build and manage AI-powered cloud infrastructure
+1000 moreAI Engineering Advanced Certification by IIT-Roorkee
Premier AI engineering certification from IIT-Roorkee
AI Forward Deployed Engineer Program
Full-stack engineering, production AI and client-facing consulting
+1000 moreExample
Example Input
Input 1:
Input 2:
Example Output
Output 1:
Output 2:
Example Explanation
Explanation 1: To create a square pattern, 5 additional tiles are needed:
These tiles are required at positions (2, 3), (3, 2), (3, 3), (4, 2), and (4, 3) (1-based indexing). This results in a square pattern with sides equal to 3, resulting in the final arrangement as: [ "EEEE", "TTTE", "TTTE", "TTTE", "EEEE" ]
Explanation 2: As there are no tiles present initially, it's sufficient to place a single tile on any block to form a square with sides equal to 1.
Hint
- Start by handling the scenario where no tiles exist initially, allowing a single tile to be placed on any block to form a base square.
- For cases where tiles are present, focus on identifying the bounding rows and columns with existing tiles to determine the required side length of the square, considering the limits of the wall's dimensions.
Complete Solution
Mesmerizing Necklace Arrangement
Jack has gifted Ava a beautiful necklace adorned with red ('R') and blue ('B') beads. However, Ava seeks to enhance its allure without altering the bead sequence.
To imbue the necklace with a mesmerizing quality, it must be divisible into three distinct sections while maintaining the bead sequence. The first and third sections should exclusively feature red beads, and the second section should consist solely of blue beads. Sections might be empty, containing no beads.
Your task is to assist Ava in determining the minimum number of beads to remove without disrupting their order, achieving the mesmerizing look she desires. You're given a string A of size N, where A[i] represents the i-th bead of the necklace.
Problem Constraints
Input Format
- The first and only argument is a string A.
Output Format
- Return an integer denoting the required answer.
Example
Example Input
Input 1:
Input 2:
Example Output
Output 1:
Output 2:
Example Explanation
Explanation 1: The necklace "RRRBBR" is already mesmerizing as it satisfies the conditions without requiring any bead removal. Therefore, the output is 0.
Explanation 2: In the necklace "BRRBR", by removing the first bead ('B'), the sequence becomes "RRBR", satisfying the conditions for a mesmerizing necklace. Thus, only one bead needs to be removed to achieve the mesmerizing configuration.
Hint
- Generate prefix arrays to count 'R' and 'B' beads in the necklace prefixes.
- Utilize a two-pointer approach (nested loops) to find the optimal i and j positions.
How Scaler Transformed Careers in Different Fields
Scaler learners achieved 2.5x salary growth with average post-Scaler CTC reaching ₹23L.
Google
Amazon
Microsoft
Flipkart
Adobe1200+ moreComplete Solution
Replacement Score
Given a binary string A consisting of only ‘0’ and ‘1’, the score of the string is defined as the maximum number of replacements you can perform on a string if you can replace “00” with “0” in one removal. You also need to process some queries given in the form of 2 arrays B and C where the ith query denotes that B[i] index of A needs to be replaced by the character C[i] where B[i] is an index and a C[i] is a character(‘0’ or ‘1’). You need to calculate the score after each query.
Problem Constraints
Input Format
- The first argument is a string A.
- The second argument is a vector of integers denoting the index for each query.
- The third argument is a vector of characters denoting the character to be replaced within each query.
Output Format
- Return an integer array containing the answer to each query.
Example
Example Input
Input 1:
Input 2:
Example Output
Output 1:
Output 2:
Example Explanation
Explanation 1: After the first query, the string is “0110”. The score is 0 as we can’t replace anything. After the second query, the string is “0010”. The score is 1 as we can replace one “00”. After the third query, the string is “0011”. The score is 1 as we can replace one “00”. After the fourth query, the string is “0001”. The score is 2 as we can replace 2 times.
Explanation 2: After the first query, the string is “0” and the score is 0.
Turn Learning into Career Growth
Hint
- The number of consecutive 0s gives the answer.
- Only the left and the right index matter during a query.
Complete Solution
Maxed Arrays
An array of integers X of length N is called Maxed with respect to a particular element K inside it if:
- 3 <= N
- If the index of the element K is i, then 1 < i < N
- max(X[1], … , X[i]) ≠ max(X[2], … , X[i])
- max(X[i], … , X[N]) ≠ max(X[i], … , X[N-1])
Given an array A of integers, for each element in A from index 1 to |A|, you need to find the sum of the length of all the subarrays of A that are Maxed with respect to each of these elements. Output is an array B where B[i] denotes the sum of the length of all the Maxed subarrays with respect to A[i].
Problem Constraints
Input Format
- The first argument is an integer array A.
Output Format
- Return an integer array, the answer for each element in A.
Example
Example Input Input 1:
Input 2:
Example Output
Output 1:
Output 2:
Example Explanation
Explanation 1:
There is no subarray for the 0th element because it would always be the first element in each subarray. For the 1st element, there is only the subarray [0, 2, 1] which satisfies the first 2 conditions. But it doesn’t satisfy the 2nd condition as max(0, 2) = max(2). There is no subarray for 2nd element because it would always be the last element in each subarray.
Explanation 2:
There is no subarray for the 0th element because it would always be the first element in each subarray. The 2 subarrays that satisfy the conditions for the 1st element are [5, 3, 2, 5] and [5, 3, 2, 5, 7]. The sum of lengths is 4 + 5 = 9. A total of 4 subarrays satisfy the conditions for the 2nd element - [5, 3, 2, 5], [5, 3, 2, 5, 7], [3, 2, 5, 7] and [3, 2, 5]. Sum = 3 + 4 + 4 + 5 = 16. No subarray satisfies the conditions for the 3rd and 4th elements.
Hint
- Stacks can be used to have a list of increasing maximums on one side for each element.
