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).
- Use a pointer to track the index for the next non-zero element.
- Iterate through the array, placing non-zero elements at the pointer's index.
- 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
shiftValuesmethod iterates through the input array.If a non-zero value is found, it is placed at the current
pointerindex, and the element at the current index is replaced with 0.The
pointeris 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
pointerwithout 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
Top comments (0)