Shifting Non-Zero Values Right : A Common Array Interview Problem-2

Introduction

In this post, we'll explore how to shift all non-zero values in an array to the right while maintaining their relative order. This problem is a common interview question that tests your understanding of array manipulation and algorithm optimization. Let's dive into the solution using Java.

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, we want to shift all non-zero values to the right while preserving their order. The zero values should be moved to the left.

Example:

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

Approach

We’ll use an index-tracking approach to solve this problem. The goal is to iterate through the array from right to left and shift non-zero elements to their correct positions.

1. Initialize a Pointer: Start by setting a pointer at the last index of the array. This pointer will mark where the next non-zero value should be placed.
2. Traverse the Array: Move through the array from right to left. For each non-zero element encountered, place it at the position indicated by the pointer and decrement the pointer.
3. Remaining Zeros: After all non-zero elements have been repositioned, any unused spots at the beginning of the array (i.e., to the left of the pointer) will automatically contain zeros.

This approach has a time complexity of O(n) and a space complexity of O(1), making it both efficient and space-saving.

Implementation

package arrays;

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

    private void shiftValues(int[] inputArray) {

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

        // If value is Non-Zero then place it at the pointer index
        for (int i = pointer; i >= 0; i--) {

            /* If there is a non-zero already at correct position,
               just decrement 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 : Ending with a Non-Zero
        int input1[] = { 1, 2, 0, 3, 0, 0, 4, 0, 2, 9 };

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

        // 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[];

        ShiftNonZeroValuesToRight classObject = new ShiftNonZeroValuesToRight();
        classObject.shiftValues(input1); // Result : 0000123429
        classObject.shiftValues(input2); // Result : 0008515
        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 of the Code

1. shiftValues Method:
   • Input Parameter: inputArray – The array that needs to be processed.
   • Pointer Initialization: pointer is initialized to the last index of the array.
   • Array Traversal: The loop iterates from the end of the array toward the beginning, checking for non-zero elements. Non-zero elements are moved to the position indicated by the pointer, and the pointer is decremented.
   • Result: Once all non-zero elements are moved, the remaining elements in the array will naturally be zeros without any additional steps.
2. Main Method:
   • The main method contains various test cases to demonstrate different scenarios, such as arrays ending with a non-zero or zero value, arrays with all zeros or all non-zeros, empty arrays, and uninitialized arrays.

Edge Cases Considered

• Empty Arrays: The program handles empty arrays without throwing an exception.

• Uninitialized Arrays: Uncommenting the test case for uninitialized arrays will result in a compilation error, demonstrating the importance of array initialization.

Conclusion

This program provides an efficient way to shift non-zero values to the right in an array. It is a great example of how careful pointer management can lead to optimal solutions in terms of both time and space complexity.

For another common interview question on arrays, check out my previous post on Shifting Non-Zero Values Left: A Common Array Interview Problem-1

Related Posts

• Java Fundamentals
• Java Memory Essentials
• Java Keywords Essentials
• Java OOPs Essentials
• Collections Framework Essentials

If you have any questions or suggestions, feel free to leave a comment below. Happy coding!