702780. Split the Array
Medium
Split the Array
Slug: split-the-array0238
Difficulty: Medium
Id: 702780
Topic Tags: Arrays, Bit Magic, Data Structures
Company Tags: None
Summary
Given an array of integers, split it into two arrays such that one array has all odd numbers and the other array has all even numbers. The original order of elements should be maintained in both arrays.
Detailed Explanation
To solve this problem, we can use a simple two-pointer approach. Initialize two pointers, odd and even, at the beginning of the array. Then, iterate through the array, checking each element to see if it's odd or even. If an element is odd, move the odd pointer one step forward; if it's even, move the even pointer one step forward.
Here's a step-by-step breakdown:
- Initialize
oddandevenpointers at the beginning of the array. - Iterate through the array:
- If the current element is odd, add it to the
oddarray and increment theoddpointer. - If the current element is even, add it to the
evenarray and increment theevenpointer.
- If the current element is odd, add it to the
- Once the iteration is complete, return the
oddandevenarrays.
Time complexity: O(n), where n is the length of the input array. Space complexity: O(1), as we only use a constant amount of space to store the pointers and arrays.
Optimized Solutions
Java
public class SplitArray {
public static int[][] splitArray(int[] arr) {
int oddIndex = 0;
int evenIndex = 1;
int[][] result = new int[][] {new int[arr.length], new int[arr.length]};
for (int i = 0; i < arr.length; i++) {
if ((arr[i] & 1) == 0) { // Check if the number is even
result[1][evenIndex++] = arr[i];
} else {
result[0][oddIndex++] = arr[i];
}
}
return result;
}
}