Shifting Non-Zero Values Left: A Common Array Interview Problem-1

Introduction

In technical interviews, array manipulation problems are frequently encountered. In this post, we’ll tackle a common problem: Shifting non-zero values to the left while maintaining the order of non-zero elements and pushing all zeros to the right.

If you're unfamiliar with basic array concepts, I recommend checking out Understanding Array Basics in Java: A Simple Guide to get up to speed!

Problem Statement

Given an array of integers, your task is to move all non-zero elements to the left side while pushing all zero elements to the right. The relative order of the non-zero elements must be preserved.

Example:

Input:  [1, 2, 0, 3, 0, 0, 4, 3, 2, 9]
Output: [1, 2, 3, 4, 3, 2, 9, 0, 0, 0]

Approach

We can solve this problem in O(n) time using a single pass through the array, and the solution will have a space complexity of O(1).

1. Use a pointer to track the index for the next non-zero element.
2. Iterate through the array, placing non-zero elements at the pointer's index.
3. Increment the pointer each time a non-zero element is placed.

The Code

package arrays;

// Time Complexity - O(n)
// Space Complexity - O(1)
public class ShiftNonZeroValuesToLeft {

    private void shiftValues(int[] inputArray) {

        /* Variable to keep track of index position to be 
                   filled with Non-Zero Value */ 
        int pointer = 0;

        // If value is Non-Zero then place it at the pointer index
        for (int i = 0; i < inputArray.length; i++) {

            /* If there is a non-zero already at correct position, 
                     just increment position */
            if (inputArray[i] != 0) {

                if (i != pointer) {
                    inputArray[pointer] = inputArray[i];
                    inputArray[i] = 0;
                }

                pointer++;
            }
        }

        // Printing result using for-each loop
        for (int i : inputArray) {
            System.out.print(i);
        }

        System.out.println();
    }

    public static void main(String[] args) {

        // Test-Case-1 : Starting with a Non-Zero
        int input1[] = { 1, 2, 0, 3, 0, 0, 4, 3, 2, 9 };

        // Test-Case-2 : Starting with Zero
        int input2[] = { 0, 5, 1, 0, 2, 0, 9 };

        // Test-Case-3 : All Zeros
        int input3[] = { 0, 0, 0, 0 };

        // Test-Case-4 : All Non-Zeros
        int input4[] = { 1, 2, 3, 4 };

        // Test-Case-5 : Empty Array
        int input5[] = {};

        // Test-Case-6 : Empty Array
        int input6[] = new int[5];

        // Test-Case-7 : Uninitialized Array
        int input7[];

        ShiftNonZeroValuesToLeft classObject = new ShiftNonZeroValuesToLeft();
        classObject.shiftValues(input1); // Result : 1234329000
        classObject.shiftValues(input2); // Result : 5129000
        classObject.shiftValues(input3); // Result : 0000
        classObject.shiftValues(input4); // Result : 1234
        classObject.shiftValues(input5); // Result : 
        classObject.shiftValues(input6); // Result : 00000
        classObject.shiftValues(input7); // Result : Compilation Error - Array may not have been initialized
    }

}

Explanation

• The shiftValues method iterates through the input array.

• If a non-zero value is found, it is placed at the current pointer index, and the element at the current index is replaced with 0.

• The pointer is then incremented to track the next position for a non-zero element.

• If there is already a non-zero value at the correct position (i.e., at the pointer index), the method simply increments the pointer without making any swaps.

• This continues until the entire array is processed.

Time & Space Complexity

• Time Complexity: O(n), where n is the length of the array.

• Space Complexity: O(1), since we’re modifying the array in place.

Edge Cases

• All Zeros: If the array contains all zeros, it will remain unchanged.

• No Zeros: If there are no zeros, the original order of elements is preserved.

• Empty Array: The function should handle empty arrays without issues.

Conclusion

This problem showcases the importance of understanding array manipulation techniques and their efficiency in coding interviews. Mastering such problems can greatly enhance your problem-solving skills!

The above is the detailed content of Shifting Non-Zero Values Left: A Common Array Interview Problem-1. For more information, please follow other related articles on the PHP Chinese website!