This content originally appeared on DEV Community and was authored by Arshi Saxena
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.
- 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.
- 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.
- 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
-
shiftValuesMethod:-
Input Parameter:
inputArray– The array that needs to be processed. -
Pointer Initialization:
pointeris 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 thepointeris decremented. - Result: Once all non-zero elements are moved, the remaining elements in the array will naturally be zeros without any additional steps.
-
Input Parameter:
-
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
If you have any questions or suggestions, feel free to leave a comment below. Happy coding!
This content originally appeared on DEV Community and was authored by Arshi Saxena
Arshi Saxena | Sciencx (2024-09-24T14:12:34+00:00) Shifting Non-Zero Values Right : A Common Array Interview Problem-2. Retrieved from https://www.scien.cx/2024/09/24/shifting-non-zero-values-right-a-common-array-interview-problem-2/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.