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.
