<p>You are given a <strong>0-indexed</strong> integer array <code>nums</code> of <strong>even</strong> length consisting of an <strong>equal</strong> number of positive and negative integers.</p>

<p>You should return the array of nums such that the the array follows the given conditions:</p>

<ol>
	<li>Every <strong>consecutive pair</strong> of integers have <strong>opposite signs</strong>.</li>
	<li>For all integers with the same sign, the <strong>order</strong> in which they were present in <code>nums</code> is <strong>preserved</strong>.</li>
	<li>The rearranged array begins with a positive integer.</li>
</ol>

<p>Return <em>the modified array after rearranging the elements to satisfy the aforementioned conditions</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [3,1,-2,-5,2,-4]
<strong>Output:</strong> [3,-2,1,-5,2,-4]
<strong>Explanation:</strong>
The positive integers in nums are [3,1,2]. The negative integers are [-2,-5,-4].
The only possible way to rearrange them such that they satisfy all conditions is [3,-2,1,-5,2,-4].
Other ways such as [1,-2,2,-5,3,-4], [3,1,2,-2,-5,-4], [-2,3,-5,1,-4,2] are incorrect because they do not satisfy one or more conditions.  
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [-1,1]
<strong>Output:</strong> [1,-1]
<strong>Explanation:</strong>
1 is the only positive integer and -1 the only negative integer in nums.
So nums is rearranged to [1,-1].
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= nums.length &lt;= 2 * 10<sup>5</sup></code></li>
	<li><code>nums.length</code> is <strong>even</strong></li>
	<li><code>1 &lt;= |nums[i]| &lt;= 10<sup>5</sup></code></li>
	<li><code>nums</code> consists of <strong>equal</strong> number of positive and negative integers.</li>
</ul>

<p>&nbsp;</p>
It is not required to do the modifications in-place.
class Solution {
    // void helper(vector<int>& nums, vector<int>  & ans){
    //     int size = nums.size();
    //     vector<int> visited(size, 0);
         
    // for(int k = 0 ; k < size; k++){
      
    // if(k % 2 == 0){
    //     int j = 0;
    //        for(int i = 0; i < size; i++){
    //             if(nums[i] > 0 && !visited[i] ) {
    //                 j = i;
    //                 break;
    //             }

            
    //         }
    //  ans[k]=nums[j];
    //  visited[j]=1;
    
    // }
    // else { 
    //     int j = 0;
    //        for(int i = 0; i < size; i++){
    //             if(nums[i] < 0 && !visited[i] ) {
    //                 j = i;
    //                 break;
    //             }

            
    //         }
    //  ans[k]=nums[j];
    //  visited[j]=1;
    // }
 
    // }}

    // better solution  for thiss question 2 O(N)

    void helper(vector<int>& nums  ){
        int size = nums.size();
     vector<int> pos(size/2, 0);
     vector<int> neg(size/2, 0);
     int idx1=0;
     int idx2 =0;

     for(int i=0; i < size; i++ ){
        if(nums[i] < 0){
         neg[idx1] = nums[i];
         idx1++;
        }else {
        pos[idx2] = nums[i];
        idx2++;
        }
     }   
    idx1 = 0;
    idx2 = 0;

     for(int i = 0; i < size ; i++ ){
       if(i % 2 == 0 ){
          nums[i] = pos[idx1++];

       }else {

          nums[i] = neg[idx2++];
       }
        
     }}
public:
    vector<int> rearrangeArray(vector<int>& nums) {
         vector<int> ans(nums.size(), 0);
        //  helper(nums, ans);
        //  return ans;
        helper( nums);
        return nums;
     }
};
135192