Alternative and optimized solution for the given problem

Viewed 90

This was my interview question, and I am able to solve it, But left with a note from interviewer, saying this is not optimized code, I am not able to solve it in optimized solution, any one here to help.

Question : Given an array array1, rearrange the array in the format

  1. all negative and its absolue number to be inserted first in the array (Sorted).
  2. and all the remaning items should be concated to the new array (Sorted)
//input 
var array = [8,7,0,6,4,-9,-7,2,-1,3,5,1,10];
//output
var array2 = [-7,7,-1,1,-9,0,2,3,4,5,6,8,10];

My Code :

function sort(arr){  
  var arrange = arr.sort((a, b)=>{ return a-b});
  var array1=[];
  for(let i=0; i<arrange.length; i++){
    let firstItem = Math.abs(arrange[i]);
    for(let j=i+1; j<arrange.length; j++){
       if(firstItem === Math.abs(arrange[j])){
         array1.push(arrange[i], arrange[j])       
       }
   }
  }
  arrange = arrange.filter((item, i)=>{
     return array1.indexOf(item) === -1
  })
 return [...array1, ...arrange]
} 


console.log(sort(array));

JSBIN

Please give some hints also, what is wrong with my approach.

Note : The code I wrote is like o(n^2),, he wanted a O(log n), he meant , Without nested for loops , we can solve it. can we ?

4 Answers

This solution is not optimise because consumption of processing time if we ignore some loops like sort and filter complexity. it have O(n^2) complexity. that means if number of element increase it takes more time.

in that kind of question, try to ignore nested loops if possible.

There are multiple problems in your alg

  1. nested for loops: O(n2)
for(let i=0; i<arrange.length; i++){ // ----------O(n)
  let firstItem = Math.abs(arrange[i]);
  for(let j=i+1; j<arrange.length; j++){ // ---------x O(n(n+1)/2)==O(n^2)
       if(firstItem === Math.abs(arrange[j])){
         array1.push(arrange[i], arrange[j])       
       }
   }
}
  1. filter + indexOf both O(n) so O(n2) too
arrange = arrange.filter((item, i)=>{ // O(n)
   return array1.indexOf(item) === -1 // -- x O(n*n) // because indexOf is O(n)
})

May may solve it in O(nlog(n))

First possibility:

  • get the negatives, and their associated (possibly several?) positives counterpart as a map (neg => positives)
  • get the positives in another bag
  • sort the negative map (by key)
  • output the negative map, and delete the positive if any from the positive bag
  • sort the positive bag
  • output it

const v = [8,7,0,6,4,-9,-7,2,-7,7,7,-1,3,5,1,10]
function v1 (v) {
  const neg = new Map()
  const pos = new Map()
  v.forEach(el => {
    if (el >= 0) return
    if (neg.has(el)) {
      neg.get(el).push(el)
      return
    }
    neg.set(el, [el])
  })
  v.forEach(el => {
    if (el < 0) return
    if (neg.has(-el)) {
      neg.get(-el).push(el)
      return
    }
    if (pos.has(el)) {
      pos.get(el).push(el)
      return
    }
    pos.set(el, [el])
  })
  const sortedNegs = [...neg.entries()].sort((a, b) => (a[0]-b[0]))
  const output = []
  sortedNegs.forEach(([k, values]) => {
    output.push(values)
    pos.delete(-k)
  })
  const sortedPos = [...pos.entries()].sort((a, b) => (a[0]-b[0]))

  sortedPos.forEach(([k, values]) => output.push(values))
  console.log(output.flatMap(x => x))
}
v1(v)

Another shorter approach with the same spirit

  • group numbers by duplicity num => [num,...]
  • sort numbers
  • after outputting each group, look if there exists a positive counter part
  • if so output it and delete it

const v = [8,7,0,6,4,-9,-7,2,-7,7,7,-1,3,5,1,10]
function v2 (v) {

  const groups = v.reduce((m, el) => {
    return m.has(el) ? (m.get(el).push(el), m) : m.set(el, [el])
  }, new Map())
  const sortedGroups = [...groups.entries()].sort((a,b) => a[0] - b[0])
  const output = []
  sortedGroups.forEach(([k, v]) => {
    if (k < 0) {
      output.push(v)
      if (groups.has(-k)) {
        output.push(groups.get(-k))
        groups.delete(-k)
      }
      return
    }
    groups.has(k) && output.push(v)
  })
  console.log(output.flatMap(x => x))
}
v2(v)

Finally you may use indices to fasten some more but let's have a look:

const v = [8,7,0,6,4,-9,-7,2,-7,7,7,-1,3,5,1,10]
function v1 (v) {
  const neg = new Map()
  const pos = new Map()
  v.forEach(el => {
    if (el >= 0) return
    if (neg.has(el)) {
      neg.get(el).push(el)
      return
    }
    neg.set(el, [el])
  })
  v.forEach(el => {
    if (el < 0) return
    if (neg.has(-el)) {
      neg.get(-el).push(el)
      return
    }
    if (pos.has(el)) {
      pos.get(el).push(el)
      return
    }
    pos.set(el, [el])
  })
  const sortedNegs = [...neg.entries()].sort((a, b) => (a[0]-b[0]))
  const output = []
  sortedNegs.forEach(([k, values]) => {
    output.push(values)
    pos.delete(-k)
  })
  const sortedPos = [...pos.entries()].sort((a, b) => (a[0]-b[0]))

  sortedPos.forEach(([k, values]) => output.push(values))
  return output.flatMap(x => x)
}
v1(v)
function v2 (v) {

  const groups = v.reduce((m, el) => {
    return m.has(el) ? (m.get(el).push(el), m) : m.set(el, [el])
  }, new Map())
  const sortedGroups = [...groups.entries()].sort((a,b) => a[0] - b[0])
  const output = []
  sortedGroups.forEach(([k, v]) => {
    if (k < 0) {
      output.push(v)
      if (groups.has(-k)) {
        output.push(groups.get(-k))
        groups.delete(-k)
      }
      return
    }
    groups.has(k) && output.push(v)
  })
  return output.flatMap(x => x)
}
v2(v)

function slow(arr){  
  var arrange = arr.sort((a, b)=>{ return a-b});
  var array1=[];
  for(let i=0; i<arrange.length; i++){
    let firstItem = Math.abs(arrange[i]);
    for(let j=i+1; j<arrange.length; j++){
       if(firstItem === Math.abs(arrange[j])){
         array1.push(arrange[i], arrange[j])       
       }
   }
  }
  arrange = arrange.filter((item, i)=>{
     return array1.indexOf(item) === -1
  })
 return [...array1, ...arrange]
} 

(() => {
  const big = v.join(',').repeat(100).split(',')
  ;[v1, v2, slow].forEach((meth, i) => {
    console.time('time'+i) //respectively 4ms, 3ms, 1s(!)
    meth(big)
    console.timeEnd('time'+i)
  })  
})()
What I am trying to emphase is that writing for loops and incrementing the indices do increase perfs but algorithm (and their datastructure) matter more before attempting to such optimization.

Here I have an alternate solution

//input 
var array = [8,7,0,6,4,-9,-7,2,-1,3,5,1,10];
//output
var array2 = [-7,7,-1,1,-9,0,2,3,4,5,6,8,10];


console.clear();

function sort(arr){
  const singular=[];
  const arrange = arr.sort((a, b)=>{ return a-b});

  const output = arrange.flatMap((item, i)=>{
     if(item < 0 && arrange.includes(-item)){
         return [item, -item];       
     }else{
       singular.push(item);
     }     
  }).filter((item)=>{ return item; });

  const result = [...new Set(output), ...singular];

  console.log('result : ', result);
} 


console.log(sort(array));

Your solution has 2 sorts and a nested for loop which is bad for business.

Sort has complexity: O(nlog(n)) while a nested for loop has complexity: O(n^2).

When you see arrays in a problem, first of all, think about trying to solve them linearly (i.e. can we get the solution in one iteration?). Your question has a requirement of sorting, so you'll have to use a sort, there's no escaping it. As a rule of thumb, avoid using nested for loops unless absolutely necessary - with great power comes great responsibility!

Check out this solution. I won't say it is the best. But it is quite decent. It uses one sort and loops through the array twice.

function modifyArray(array) {
    var sorted = array.sort((a, b) => { return a - b });
    let map = {};
    for (var i = 0; i < sorted.length; i++) {
        map[sorted[i]] = true;
    }

    let negativesAndAbsolutes = [];
    let uniqueNegatives = [];
    let uniquePositives = [];
    let currNumber = null;


    for (var i = 0; i < sorted.length; i++) {
        currNumber = sorted[i];
        if (!map[currNumber]) {
            // already sorted.
            continue;
        }
        if (currNumber < 0) {
            if (map[-1 * currNumber]) {
                // its negative and it has an absolute.
                negativesAndAbsolutes.push(currNumber, -1 * currNumber);
                map[currNumber] = false;
                map[-1 * currNumber] = false;       // don't process it again.
                continue;
            } else {
                // unique negative.
                uniqueNegatives.push(currNumber);
            }
            continue;
        }
        uniquePositives.push(currNumber);
    }

    return [...negativesAndAbsolutes, ...uniqueNegatives, ...uniquePositives];
}

modifyArray([8,7,0,6,4,-9,-7,2,-1,3,5,1,10]);
Related