Finance[US] Career Guide Free Tutorials Go to Your University Placement Preparation 
0 like 0 dislike
1.2k views
in Coding Questions by Goeduhub's Expert (2.3k points)

Given an array arr of integers (not necessarily distinct), we split the array into some number of "chunks" (partitions), and individually sort each chunk.  After concatenating them, the result equals the sorted array.

What is the most number of chunks we could have made?

Example 1:

Input: arr = [5,4,3,2,1]
Output: 1
Explanation:
Splitting into two or more chunks will not return the required result.
For example, splitting into [5, 4], [3, 2, 1] will result in [4, 5, 1, 2, 3], which isn't sorted.

Example 2:

Input: arr = [2,1,3,4,4]
Output: 4
Explanation:
We can split into two chunks, such as [2, 1], [3, 4, 4].
However, splitting into [2, 1], [3], [4], [4] is the highest number of chunks possible.

Note:

  • arr will have length in range [1, 2000].
  • arr[i] will be an integer in range [0, 10**8].

1 Answer

0 like 0 dislike
by Goeduhub's Expert (2.3k points)
 
Best answer

Actually, the key to the problem is the idea of using stack.

When we encounter an element, the very first thing we think must be: how can we use this element and will this element still be needed?

To the first question, this element is used to determine if it must be together with the previous greater elements.

To the second question, once this element is removed, it will no longer be needed. Reason is:

Considering the array with order of 4,5,4,3, When 4 came in the stack (now 4,5), 5 was removed because 5,4 must be a chunk. Then 3 came in, does it need to know the existence of 5 and 4(the second 4)? As long as 4(the first 4) and 3 must be in the same chunk , all the elements between 4(the first 4) and 3 should be in the same chunk.

class Solution:

    def maxChunksToSorted(self, arr: List[int]) -> int:

        stack = [] # store a list of biggest element of each chunk

        for n in arr:

            m = n # the biggest element from beginning to n

            while len(stack)>0 and stack[-1]>n:

                m = max(m, stack.pop())

            stack.append(m)  # all element bigger than n was poped out of stack, so this is the biggest element

        return len(stack) # length of the chunks array

eg : ans = Solution()

ans.maxChunksToSorted([2,1,3,4,4])

Output-

4

Learn & Improve In-Demand Data Skills Online in this Summer With  These High Quality Courses[Recommended by GOEDUHUB]:-

Best Data Science Online Courses[Lists] on:-

Claim your 10 Days FREE Trial for Pluralsight.

Best Data Science Courses on Datacamp
Best Data Science Courses on Coursera
Best Data Science Courses on Udemy
Best Data Science Courses on Pluralsight
Best Data Science Courses & Microdegrees on Udacity
Best Artificial Intelligence[AI] Courses on Coursera
Best Machine Learning[ML] Courses on Coursera
Best Python Programming Courses on Coursera
Best Artificial Intelligence[AI] Courses on Udemy
Best Python Programming Courses on Udemy

Related questions

0 like 0 dislike
1 answer 127 views
asked Sep 6, 2020 in Coding Questions by Vaibhav98 Goeduhub's Expert (2.3k points)
0 like 0 dislike
1 answer 981 views
0 like 0 dislike
1 answer 1.7k views
asked Sep 10, 2020 in Coding Questions by Vaibhav98 Goeduhub's Expert (2.3k points)
0 like 0 dislike
1 answer 460 views
0 like 0 dislike
1 answer 259 views
asked Aug 31, 2020 in Coding Questions by Vaibhav98 Goeduhub's Expert (2.3k points)

 Important Lists:

Important Lists, Exams & Cutoffs Exams after Graduation PSUs

 Goeduhub:

About Us | Contact Us || Terms & Conditions | Privacy Policy ||  Youtube Channel || Telegram Channel © goeduhub.com Social::   |  | 

 

Free Online Directory

...