Solution 4 for Scaler Topics Fortnightly Contest - 25
Maxed Arrays
This article is part of the Scaler Topics Fortnightly Contest - 25
Transform Your Career
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
Solution Approach
We can first use the stacks where we keep the closest number greater than the current number. We can use the stacks from both sides because we need to find the subarrays that contain the element. Once we have both the left stack and the right stack. The only subarrays following all the conditions are those that are formed by the combination of one from the left stack and one from the right. But we can’t directly take all the pairs.
To optimize, we know that each element in the right stack needs to be acknowledged for each of the elements in the left stack. So we can simply multiply the index with the size of the left stack. Similarly, we can do this for the left stack. To do this optimally for each element, we can just maintain the index sum for each element in the stack and multiply it by the size of the other stack. The final sum of lengths for a particular element would be Sum(Right)Size(Left) - Sum(Left)Size(Right) + Size(Left)*Size(Right)
Time Complexity: O(|A|) Space Complexity: O(|A|)
C++ Implementation
Java Implementation
Scaler Placement Report and Statistics
Scaler learners achieved 2.5x salary growth with average post-Scaler CTC reaching ₹23L.
Google
Amazon
Microsoft
Flipkart
Adobe1200+ more
