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. 
