There is an array ‘A’ of size ‘N’ with an equal number of positive and negative elements.
Without altering the relative order of positive and negative numbers, you must return an array of alternative positive and negative values.
Note:
Start the array with a positive number.
For example
Input:
A = [1, 2, -4, -5], N = 4
Output:
1 -4 2 -5
Explanation:
Positive elements = 1, 2
Negative elements = -4, -5
To maintain relative ordering, 1 must occur before 2, and -4 must occur before -5.
The first line contains an integer, ‘N’.
The second line has ‘N’ integers denoting the array ‘A’.
You must return an array with alternate positive and negative values.
You don’t need to print anything. Just implement the given function.
2 <= N <= 10^5
-10^9 <= A[i] <= 10^9, A[i] != 0
N%2==0
Time Limit: 1 sec
6
1 2 -3 -1 -2 3
1 -3 2 -1 3 -2
Testcase 1:
Input:
A = [1, 2, -3, -1, -2, 3], N = 6
Output:
1 -3 2 -1 3 -2
Explanation:
Positive elements = 1, 2, 3
Negative elements = -3, -1, -2
To maintain relative ordering, 1 should come before 2, and 2 must come before 3.
Also, -3 should come before -1, and -1 must come before -2.
4
-2 -3 4 5
4 -2 5 -3
Store the positive and the negative elements separately.
Approach:
Algorithm:
Function int alternateNumber([int] A):
O( N ), Where ‘N’ is given input.
We are taking O( N ) time to fill the ‘pos’ and ‘neg’ arrays. We take O( N ) time to form the final array. Hence, the overall time complexity will be O( N ).
O( N ), Where ‘N’ is given input.
We are taking O( N ) extra space for storing the positive and the negative values. Hence, the overall space complexity will be O( N ).
All tags
Sort by
Interview problems
Alternate Numbers (java)
import java.util.ArrayList;
public class Solution {
public static int[] alternateNumbers(int []a) {
// Write your code here.
ArrayList pos = new ArrayList<>();
ArrayList neg = new ArrayList<>();
for(int i=0; i<a.length; i++){
if (a[i] > 0) {
pos.add(a[i]);
} else {
neg.add(a[i]);
}
}
for(int i=0; i<a.length/2; i++){
a[2*i] =(int) pos.get(i);
a[2*i+1] =(int) neg.get(i);
}
return a;
}
}
Interview problems
time and space is O(N)
#include<bits/stdc++.h>
vector<int> alternateNumbers(vector<int>&a) {
int n = a.size();
vector<int> ans(n, 0);
int posIndex = 0;
int negIndex = 1;
for (int i = 0; i < n; i++) {
if (a[i] > 0) {
ans[posIndex] = a[i];
posIndex += 2;
}
else {
ans[negIndex] = a[i];
negIndex += 2;
}
}
return ans;
}
// Time Complexity = O(N)
// Space Complexity = O(N)
Interview problems
BETTER THAN 100%
vector<int> alternateNumbers(vector<int>&a) {
// Write your code here.
int n = a.size();
vector<int> ans(n,0);
int posIndex = 0, negIndex = 1;
for(int i =0 ; i < n ; i++){
if( a[i] < 0){
ans[negIndex] = a[i];
negIndex += 2;
}
else {
ans[posIndex] = a[i];
posIndex += 2;
}
}
return ans;
}
Interview problems
Easiest 14ms code
#include<bits/stdc++.h>
vector<int> alternateNumbers(vector<int>&a) {
vector<int> pos;
vector<int> neg;
for(int i = 0; i < a.size(); i++)
{
if(a[i] > 0)
{
pos.push_back(a[i]);
}
else
{
neg.push_back(a[i]);
}
}
for(int i = 0; i < a.size()/2; i++)
{
a[2 * i] = pos[i];
a[2 * i + 1] = neg[i];
}
return a;
}
Interview problems
C++ Easy and Simple Solution
vector<int> alternateNumbers(vector<int>&a) {
// Write your code here.
int n = a.size();
vector<int> ans(n,0);
int posIndex = 0;
int negIndex = 1;
for(int i = 0;i<n;i++){
if(a[i]<0){
ans[negIndex] = a[i];
negIndex+=2;
}
else{
ans[posIndex] = a[i];
posIndex+=2;
}
}
return ans;
}
Interview problems
Simple solution with explanation in comments
vector<int> alternateNumbers(vector<int>&a) {
int n=a.size();
int pos=0;
int neg=1;
vector<int>ans(n,0);
for(int i=0; i<n; i++)
{
if(a[i]<0) // if num is less than 0 means it's neg and placed in odd index like 1(for starting)
{
ans[neg]=a[i];
neg+=2; // once placed another number will be placed in 3,5,7 that's why increasing with 2
}
else
{
ans[pos]=a[i]; // same logic as in odd , here even will be stored in 0,2,4,6,8 ........
pos+=2;
}
}
return ans;
}
Interview problems
beats 100%|| better than 99.76% in memory
vector<int> alternateNumbers(vector<int>&a) {
// Write your code here.
int n=a.size();
vector<int>ans;
vector<int>pos;
vector<int>neg;
for(int i=0;i<n;i++){
if(a[i]>0){
pos.push_back(a[i]);
}
else{
neg.push_back(a[i]);
}
}
for(int i=0;i<pos.size();i++){
ans.push_back(pos[i]);
ans.push_back(neg[i]);
}
int k=0;
while(k<=n-2){
if(ans[0]<0){
swap(a[k],a[k+1]);
}
k=k+2;
}
return ans;
}
Interview problems
100% runtime || 99.75% Memory || c++ || time : 0{n) || space 0(n) ||
vector<int> alternateNumbers(vector<int> &a) {
// Write your code here.
vector<int> ans(a.size(),0);
int p = 0,n = 1;
for (int i = 0; i < a.size(); i++){
if (a[i] < 0) {
ans[n] = a[i];
n+=2;
} else{
ans[p] = a[i];
p+=2;
}
}
return ans;
}
Interview problems
100% runtime || 99.75% Memory || c++ || time : 0{n) || space 0(n) ||
vector<int> alternateNumbers(vector<int>&nums) {
vector<int> result(nums.size(),0);
int po=0;
int ne=1;
for(auto it :nums){
if(it>0){
result[po]=it;
po+=2;
}else{
result[ne]=it;
ne+=2;
}
}
return result;
}Interview problems
CPP Solution || can you tell its TC ?
vector<int> alternateNumbers(vector<int>&a) {
// Write your code here.
int j =0;
int n=a.size();
for(int i=0;i<a.size();i++){
if(i%2==0 && a[i]<0){ // for all even positions
j=i+1;
while (j < n && a[j] < 0) {
j++;
if (j == n)
return a;
}
// swap(a[i],a[j]);
int temp=a[j];
for(int k=j;k>i;k--){
a[k]=a[k-1];
}
a[i]=temp;
}
else if(i%2!=0 && a[i]>0){ // for all odd positions
j=i+1;
while(j<n && a[j]>0){
j++;
if(j==n) return a;
}
// swap(a[i],a[j]); // no swap to maintain the order
int temp=a[j];
for(int k=j;k>i;k--){ // instead shift elements
a[k]=a[k-1];
}
a[i]=temp;
}
}
return a;
}
