Leetcode: Steps to Make Array Non-decreasing

Question

I was trying out leetcode's Steps to Make Array Non-decreasing
As per the challenge's description:

You are given a 0-indexed integer array nums. In one step, remove all elements nums[i] where nums[i - 1] > nums[i] for all 0 < i < nums.length.

Return the number of steps performed until nums becomes a non-decreasing array.

Example 1:

Input: nums = [5,3,4,4,7,3,6,11,8,5,11] Output: 3 Explanation: The following are the steps performed:

• Step 1: [5,3,4,4,7,3,6,11,8,5,11] becomes [5,4,4,7,6,11,11]
• Step 2: [5,4,4,7,6,11,11] becomes [5,4,7,11,11]
• Step 3: [5,4,7,11,11] becomes [5,7,11,11] [5,7,11,11] is a non-decreasing array. Therefore, we return 3.

Constraints:

• 1 <= nums.length <= 1e5
• 1 <= nums[i] <= 1e9

Even though it doesn't mention any Big O constraint with regards to memory overheads, I am trying to build a solution that runs in O(n) time complexity along with O(1) memory overhead.

So far here is my solution in Java:

class Solution {
 private static void swap(int[] arr, int i, int ni) {
 int temp = arr[i];
 arr[i] = arr[ni];
 arr[ni] = temp;
 }
 public int totalSteps(int[] nums) {
 // Taking care of constraints given in challenge
 if (nums.length == 0
 || nums.length == 1
 || nums.length > Math.pow(10, 5)) {
 return 0;
 }
 // if array of size 2, O(1) check steps
 if (nums.length == 2)
 return nums[0] > nums[1] ? 1 : 0;
 // how many items removed in one full loop cycle
 int totalRemovedInACompleteLoop = 0;
 int steps = 0;
 for (int i = nums.length; i >= 1; i--) {
 // PS: this one is a temporary fix, refactor code for better approach
 // resolve resetting i at end
 // to re run a loop without going out of bound index
 if (i == nums.length)
 i -= 1;
 // -- temporary - to refactor--//
 // skip if already removed
 if (nums[i] == -1)
 continue;
 if (nums[i - 1] == -1) {
 // swap by moving removed (-1) nb to right
 swap(nums, i, i - 1);
 continue;
 }
 if (nums[i - 1] > nums[i]) {
 nums[i] = -1;// mark as removed
 ++totalRemovedInACompleteLoop;// increment counter
 }
 // Done or need to reloop?
 if (i == 1 && totalRemovedInACompleteLoop > 0) {
 i = nums.length;
 ++steps;
 totalRemovedInACompleteLoop = 0;
 }
 }
 return steps;
 }
}

My solution so far passes 83/87 tests, until It reaches a test where the nums array's size is \10ドル^5\$. When the array is of that size I get "Time Limit Exceeded". (PS: I had similar issues while trying leetcode's First missing Positive)

Note:

• This code while it works, will be refactored later on once i know which approach to follow for O(n) speed.
• I am aware that so far this solution's time complexity is \$O(n^2)+\$ and not \$O(n)\$
• When an item is removed it gets marked as "-1", I am modifying inputs of array in place.
• I could have used some DS to help (like stack, list etc..) and write another solution ( I saw several solutions posted there do that). But I want to make it work with O(1) memory overhead.
  

My question is: Can the approach I am following so far be done in O(n) time if ones insists on going with O(1) memory overhead? if yes, what algorithms should I read about and follow through to modify my code, and/or what are your suggestions? (The point here is that I am trying to expand my knowledge in areas where it lacks)

Example and output of this code so far:

int[] nums = new int[]{5, 3, 4, 4, 7, 3, 6, 11, 8, 5, 11}; //expected 3
Step 1: ie when for loop cycle finishes and before relooping
--> array [5, -1, 4, 4, 7, -1, 6, 11, -1, -1, 11]
// ie [5,4,4,7,6,11,11]
Step 2: ie when for loop cycle finishes and before relooping
--> array [5, -1, -1, 4, 7, -1, -1, 11, 11, -1, -1]
//ie [5,4,7,11,11]
Step 3: ie when for loop cycle finishes and before relooping
--> array [5, -1, -1, -1, 7, 11, -1, -1, 11, -1, -1]
// ie [5,7,11,11]
> Final array [5, 7, -1, -1, -1, 11, 11, -1, -1, -1, -1]
> Done in 3 Steps.

• TorbenPutkonen: What a weird assignment which to me brings in mind the golden rule of "never attribute to malice that what can be explained with incompetence". What they are looking for is not "steps to make a list non-decreasing," since the number of steps is always one: you perform the operation in one pass. What they are looking for is "shortest non-increasing subset" and for the given example, that is 2, not 3, since the correct result is [3,4,4,7,11,11]. My advice would be to move on and stop wasting time on this challenge, because it was not made by someone you should take advice from. :)
• TorbenPutkonen: What I mean is that the assignment is so badly worded and vague that it's not worth using your free time on. On the other hand, if you got paid to fulfill badly defined requests, that's a completely different thing. That would be called "work." :D
• ccot: @TorbenPutkonen you have a point, at first I found it badly worded. I only knew what they are actually looking for when checking step 1 in their example, precisely "...11,8,5..." where both 8,5 would be removed. It was clear they were looking into subsets.
• Martin Frank: i totally agrre with @TorbenPutkonen - i have seen very strange assignments on different coding-challanges. Some are very good and help you in gaining understanding of algorithms, but some are simply a waste of time
• ccot: @MartinFrank indeed, I tried 4 different solutions in total, the more i try the stranger this assignment seems. You and Toben are 100% right

Answer 1

integer vs. float

 || nums.length > Math.pow(10, 5)) {

Clearly an exact representation of 1e5 will easily fit within a double.

It's not obvious to me that pow is guaranteed to return 1e5. An implementation based on natural logs could easily introduce ULP errors. And then we're left wondering which side of 1e5 the answer lands on. So you're essentially asking the Gentle Reader to perform a quick experiment or go consult the pow docs:

If both arguments are integers, then the result is exactly equal to the mathematical result of raising the first argument to the power of the second argument if that result can in fact be represented exactly as a double value.

Simply writing 1e5 in the source code would have more clearly conveyed Author's Intent.

spurious special case

 if (nums.length == 2)

I fail to see how being passed "a pair" is in any interesting way different from being passed "a vector".

If you notice the main body of code fails to handle a pair correctly, then fix up the main body rather than tack on a kludge.

trashed input parameter

Caller passed in a bunch of ints. The contest specification did not require that they be modified. You didn't document that they will be swapped -- not in /** javadoc */, not even in a /* comment */. This is a POLA violation.

Months down the road, some poor maintenance engineer will get tripped up by this. Do not plant such landmines for future folks to find.

Also, the contest problem doesn't ask you to reproduce any reduced-size lists that appear in the examples. It only requires a single integer result value, so stick to that. Doing "extra work" can result in Time Limit Exceeded.

simpler algorithm

A linear scan which computes max length of deleted spans would suffice.

def total_steps(a: list[int]) -> int:
 total_count = count = 0
 if not a: # not strictly needed, since input is specified to be nonempty
 return total_count
 # lowest acceptable number for remaining entries to the right
 lowest = a[0]
 for val in a:
 if val < lowest:
 count += 1 # extend a "discard" span of entries
 else:
 total_count = max(total_count, count)
 count = 0 # we're back to accepting monotonic entries
 lowest = max(lowest, val)
 return max(total_count, count)

import unittest
class NonDescendingTest(unittest.TestCase):
 def test_non_descending(self) -> None:
 self.assertEqual(0, total_steps([]))
 self.assertEqual(3, total_steps([5, 3, 4, 4, 7, 3, 6, 11, 8, 5, 11]))
 self.assertEqual(0, total_steps([4, 5, 7, 7, 13]))
 self.assertEqual(1, total_steps([4, 3]))
 self.assertEqual(1, total_steps([4, 3, 5]))
 self.assertEqual(2, total_steps([4, 3, 3]))
 self.assertEqual(2, total_steps([4, 3, 3, 5]))
 self.assertEqual(1, total_steps([4, 3, 14, 13]))
 self.assertEqual(2, total_steps([4, 3, 3, 14, 13]))
 self.assertEqual(3, total_steps([4, 3, 3, 3, 14, 13]))
 self.assertEqual(0, total_steps(list(range(1, 1_000))))
 self.assertEqual(999, total_steps(list(range(1_000, 0, -1))))

• TorbenPutkonen: I would add that checking the input length against the 1e5 limit is a bit half-baked approach because they are not also checking the array values against the 1e9 limit. Unless there is an optimization that only works below 1e5 items, I would not bother with that check since they are already relying on the input being correct anyway.
• ccot: @J_H thanks for the detailed feedback. I tried your solution, it didn't pass when nums is [10,1,2,3,4,5,6,1,2,3]. It gives ouput 9 wile expected is 6 (as per leetcode's submission results)
• Unmitigated: Only maintaining the lowest value is incorrect. A monotonic stack would be appropriate.
• ccot: @Unmitigated yeah seems the only correct approach going with a monotonic stack.

Answer 2

Update

After several trials and coming up with multiple approaches, this exercise is not solvable in O(1) memory space/ with O(n) time complexity - to the best of my knowledge and trials past couple of days.
A better and more adequate solution is to use an extra DS like monotonic stack. Otherwise you can check a top solution on leetcode.

---

Original Answer

I have found a potential O(1) memory overhead solution,but haven't finished coding it. I will post it in pseudo code/ Graphical (@Moderators: if this is not where I should post it but better edit my original question and add it as an update, please advise). I am drained a bit from this assignment for the moment.

page 1 page 2 page 3

PS: will not mark it as accepted, since no code yet provided. If anyone codes it before I do, will accept your answer.