702832. Strange Sort
Strange Sort
Slug: strange-sort4316 Difficulty: Easy Id: 702832 Topic Tags: Arrays, Sorting, STL, Data Structures, Algorithms Company Tags: None
Summary
The Strange Sort problem involves sorting an array of integers in a specific manner. The goal is to sort the array such that all even numbers are on the left side and all odd numbers are on the right side. This means that if there are multiple even or odd numbers, they should be maintained in their original relative order.
Detailed Explanation
To solve this problem, we can use a two-pointer approach. We initialize two pointers, one at the beginning of the array (left) and one at the end of the array (right). We then enter a loop where we continuously move the pointer that points to the smaller element towards the other pointer until they meet in the middle.
Here is a step-by-step breakdown of the solution:
- Initialize two pointers,
leftandright, both pointing to the first element of the array. - Enter a loop that continues until
leftmeets or crossesright. - Inside the loop:
- Compare the elements at
leftandrightpositions. - If the element at
leftis even, moveleftone step forward. - If the element at
rightis odd, moverightone step backward. - If the element at
leftis odd and the element atrightis even, swap these two elements and then move both pointers towards each other (eitherleftorrightcan be moved first).
- Compare the elements at
- Once
leftmeets or crossesright, the array is sorted.
Time complexity: O(n), where n is the size of the input array. Space complexity: O(1), as we are only using a constant amount of space to store the pointers and variables.
Optimized Solutions
Java
public class Main {
public static void strangeSort(int[] arr) {
int left = 0;
int right = arr.length - 1;
while (left < right) {
if ((arr[left] % 2 == 0 && arr[right] % 2 != 0) ||
(arr[left] % 2 != 0 && arr[right] % 2 == 0)) {
// Swap elements
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
} else if (arr[left] % 2 < arr[right] % 2) {
left++;
} else {
right--;
}
}
}
public static void main(String[] args) {
int[] arr = {4, 3, 1, 6, 7};
strangeSort(arr);
for (int i : arr) {
System.out.print(i + " ");
}
}
}