DEV Community

Cover image for Shifting Non-Zero Values Left: A Common Array Interview Problem-1
Arshi Saxena
Arshi Saxena

Posted on • Edited on

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

#java #arrays #programming #interview

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]
Enter fullscreen mode Exit fullscreen mode

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 } }
Enter fullscreen mode Exit fullscreen mode

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!

For another common interview question on arrays, check out my next post in the series on Shifting Non-Zero Values Right : A Common Array Interview Problem-2

Related Posts

Happy Coding!

Top comments (0)