Rearrange Array by Sign
Two Pointers & Sliding Window DSA practice problem on Onlearn.
Difficulty: medium.
Topics: Rearrange an array of positive and negative numbers alternately, preserving order, Arrays, Time Complexity, Space Complexity, Big O Notation, Loops, Conditional Statements, two pointer technique, array partitioning, time complexity analysis, array manipulation, Partitioning Strategies.
Rearrange Array Elements by Sign You are given an array A of size N containing positive and negative integers. Your task is to rearrange the elements of A such that positive and negative numbers appear alternately. The rearrangement must satisfy the following conditions: 1. The relative order of positive elements among themselves must be maintained. 2. The relative order of negative elements among themselves must be maintained. 3. The rearranged array should start with a positive element. 4. If there are more positive elements than negative, or vice versa, the remaining elements of the more frequent type should be appended to the end of the array, maintaining their relative order. Input Specification The first line contains a single integer N (1 <= N <= 10^5), the size of the array. The second line contains N space separated integers representing the elements of array A ( 10^9 <= A[i] <= 10^9). Output Specification Print the N space separated integers of the rearranged array. Sample Test Cases Example 1: Input: Output: Explanation: Positive elements in order: [1, 2, 3, 4] Negative elements in order: [ 4, 5] First, alternate as many as possible: (1, 4), (2, 5). Result so far: [1, 4, 2, 5]. Remaining positive elements: [3, 4]. Append them to the end: [1, 4, 2, 5, 3, 4]. Example 2: Input: Output: Explanation: Positive elements in order: [3, 5] Negative elements in order: [ 1, 2, 4, 6] First, alternate as many as possible (starting with positive): (3, 1), (5, 2). Result so far: [3, 1, 5, 2]. Remaining negative elements: [ 4, 6]. Append them to the end: [3, 1, 5, 2, 4, 6].