Giving TLE for one test case

#1

Wrote the brute force solution on my own.

Giving TLE for one test case-

#2

Yes brute force approach will be like this only, now think something related to map. And then try to solve as the test case you are failing is because it would be solved using optimized approach using maps.

1 Like
#3

What is the use of the position array that was mentioned in the hint video? How will it help?

#4

Now you are clear with the brute force, now think it by using hashmap or unordered map. The hint to solve the problem is that the given array will always contain permutation of the first N natural numbers.(that is number from 1…N). So we will prepare a map which will contain element as the key and the index at which it is present as the value.
So do what,

  1. Create the map by filling the number as the key and the index at which it is present as the value
  2. Iterate over the whole array.
  3. For element at a particular index m we will check if it is present at its best spot or not.
  4. The best spot of any number num is the N-num index of the array.
  5. If the number is not present at its best spot then we will swap the number with element present at that spot.
  6. As we have stored the index of every element in the map we can easily retrieve that from the map to get the swap done.
#5

I tried to optimize it using map but i think the code again came out to be a brute force one, now giving TLE for 2 cases :stuck_out_tongue:

Code - https://ide.codingblocks.com/s/407081

I didn’t know how to optimize the printing of the map, can you check once.

Can you help me optimize this approach?

#6

Use unordered map instead of map, and then let me know if it gets accepted or not.

#7

Yup, still giving TLE

#8

Check Now =>

#9

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

1 Like