algoadvance

Given a fixed-length integer array arr, duplicate each occurrence of zero, shifting the remaining elements to the right. Note that elements beyond the length of the original array are not written. The array’s length should stay the same after modifying the input.

Example:

Input: arr = [1,0,2,3,0,4,5,0]
Output: [1,0,0,2,3,0,0,4]

Constraints:

Clarifying Questions

  1. Q: Can I use extra space to store intermediate values?
    • A: Ideally, the solution should be done in-place with O(1) extra space.
  2. Q: Are there any negative numbers, float numbers, or non-integer elements in the array?
    • A: No, the elements will always be integers between 0 and 9 inclusive.

Strategy

To solve this problem in-place, we’ll adopt a two-pass approach:

  1. First Pass:
    • Traverse the array to count zeros, limited by the effective length which does not consider the overflow part caused by duplication.
  2. Second Pass:
    • We’ll work backwards filling the array with duplicated zeros where needed without overwriting elements prematurely.

This strategy ensures that we correctly duplicate zeros within the array length constraints.

Detailed Steps:

  1. Traverse the array to count zeros. Determine the last index i of the original array whose value will remain within bounds after duplications.
  2. Iterate backward from this last valid position, duplicating zeros where necessary and shifting elements appropriately. Ensure no element exceeds the original array bounds.

Code

def duplicateZeros(arr):
    n = len(arr)
    zeros = 0

    # First pass: count zeros till the effective end
    for i in range(n):
        if i + zeros >= n:
            break
        if arr[i] == 0:
            # Check if zero can't be duplicated because it would exceed length
            if i + zeros == n - 1:
                arr[n - 1] = 0  # edge case: single zero making end of array
                n -= 1
                break
            zeros += 1
    
    # Second pass: start from the end and duplicate zeros while shifting elements
    for i in range(n - 1, -1, -1):
        if i + zeros < len(arr):
            arr[i + zeros] = arr[i]
        if arr[i] == 0:
            zeros -= 1
            if i + zeros < len(arr):
                arr[i + zeros] = 0

# Example usage
arr = [1,0,2,3,0,4,5,0]
duplicateZeros(arr)
print(arr)  # Output should be [1,0,0,2,3,0,0,4]

Time Complexity

The time complexity of the solution is O(n), where n is the length of the array. This is because we are performing a linear scan to count zeros and another linear scan to shift elements and duplicate zeros.

Space Complexity

The space complexity is O(1), as we are modifying the array in-place without using any additional data structures that depend on the input size.

Try our interview co-pilot at AlgoAdvance.com