vaibhavmisra's blog

Minimum operations to sort an array
By vaibhavmisra, history, 3 years ago, In English

Operation : Change any array element to arbitrary integer, O(N^2) would give TLE, My approach : ans = Length of array — Length of longest non-decreasing sub-sequence because I want maximum length already sorted, TC : O(NlgN),
Is this approach correct? Any other approaches?

  • Vote: I like it
  • +11
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
3 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

I think you're right. Since changing an element can be seen as simply delete it, the problem is actually finding a longest sorted subsequence. Thus it's indeed a LIS problem.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This problem is from a hiring challenge.

→ Reply