702839. Friendly Array
Basic
Friendly Array
Slug: friendly-array2009
Difficulty: Basic
Id: 702839
Topic Tags: Arrays, Sorting, Data Structures, Algorithms
Company Tags: None
Summary
The Friendly Array problem involves rearranging a given array of integers in a specific order. The goal is to sort the array such that all negative numbers come first, followed by zeros, and then positive numbers. This problem requires basic understanding of arrays and sorting concepts.
Detailed Explanation
To solve this problem, we will use a two-pointer approach to separate the negative numbers from the rest of the array. Here's a step-by-step breakdown:
- Initialize three pointers:
neg,zero, andpos. Setnegto 0, and setzeroandposto the beginning of the array. - Iterate through the array:
- If the current element is negative, swap it with the element at index
neg, incrementneg, and move on to the next element. - If the current element is zero, just move on to the next element (since zeros can be in any position).
- If the current element is positive, swap it with the element at index
pos, incrementpos, and move on to the next element.
- If the current element is negative, swap it with the element at index
- Once the iteration is complete, return the rearranged array.
Here's a diagram illustrating this process:
[−1, 0, 2, −3, 4, 0] → [−1, −3, 0, 0, 2, 4]
Time complexity: O(n), where n is the length of the array. Space complexity: O(1) since we're not using any extra space.
Optimized Solutions
Java
public class FriendlyArray {
public static int[] friendlyArray(int[] arr) {
int neg = 0;
int pos = arr.length - 1;
for (int i = 0; i <= pos; i++) {
if (arr[i] < 0) {
swap(arr, neg++, i);
} else if (arr[i] > 0) {
swap(arr, i, pos--);
}
}
return arr;
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}