Sort one array base on another array

Question

The problem is as below:

Two archery teams A and B compete with the same number of members. If the score of team A[i] is higher than that of team B[i], the total score of team A will be +1, so given team A and B with any number of members, please calculate how total score of team A will be the highest value and write down the best order of team A members.

Input: A = [2,7,11,15]; B = [1,10,4,11];

Output: [2,11,7,15]

This is the question asked in a group, I don't know other test cases. So I change the order of team A, B to test my code.

Here is my code:

function sortTeam(a, b){
    let result = [];
    const asort = a.slice().sort((a,b) => a - b);
    for (let i = 0; i < b.length; i++){
        let bi = b[i];
        for (let j = 0; j < asort.length; j++){
            let aj = asort[j];
            if (!result.includes(aj) && aj > bi){
                result.push(aj);
                break;
            }
        }
    }
    //console.log('result', result);
    return result;
}

Here is the version of using splice to reduce complexity:

function sortTeam(a, b){
    let result = [];
    const asort = a.slice().sort((a,b) => a - b);
    for (let i = 0; i < b.length; i++){
        let bi = b[i];
        for (let j = 0; j < asort.length; j++){
            let aj = asort[j];
            if (aj > bi){
                result.push(aj);
                asort.splice(j, 1);
                break;
            }
        }
    }
    //console.log('result', result);
    return result;
}

My questions are:

• Is there a way that I can reduce the complexity of this code?
• I can remove the includes check by using splice on asort but it's still 2 loops. And splice mutates the array -> should I use it? (I'm not into FP in anyway, just asking in general)
• As for FP, I was trying to using forEach but it doesn't let me using break, so if you guys have a FP version, please let me know (reduce is kind of a normal for-loop to me, I mean the look doesn't clean as other high order functions)
• What kind of problem is this? (I want to know the pattern or name so that I can find more similar problems to practice)

Answer 1

From a short review

• asort is not a great name, sortedA could have been better?
• As mentioned by another user, it is bad practice to change lists you receive as a parameter
• You only us bi once. I would use b[i] in that one place for readability
• aj is not a great name, your two letter variables make your code hard to read
• Once you realize that you can just match equal relative strenghths, the code can be easier
• A number of the let statements could and should be const statements

This is my rewrite;

let a = [2,7,11,15]; 
let b = [1,10,4,11];

function stackTeam(ourTeam, theirTeam){

  const ourTeamSorted = Array.from(ourTeam).sort((a,b)=>a-b);
  const theirTeamSorted = Array.from(theirTeam).sort((a,b)=>a-b);
  const out = [];

  //Go over every opposing player in the order of their team
  for(let player of theirTeam){
    const playerPosition = theirTeamSorted.indexOf(player); 
    //deal with opposing players with equal score
    theirTeamSorted[playerPosition] = undefined
    out.push(ourTeamSorted[playerPosition]);
  }
  return out;
}

  console.log("Expected:", [2,11,7,15]);
  console.log(stackTeam(a, b));

Answer 2

Verifying assumptions

The implementation only works under some assumptions not mentioned in the problem statement:

• There exists an ordering of A such that for all index i, A[i] > B[i]
• There are no duplicate values in A

If any of these assumptions is not true, the implementation will produce incorrect results (smaller array than the original).

Also, the implementation mutates one of the input arrays, effectively assuming this is acceptable.

It's important to clarify and verify assumptions in order to solve the right problem, correctly.

Inefficient algorithm

For each element of B, the implementation loops over elements of A. As often the case with such nested loops, the algorithm has \$O(n^2)\$ time complexity.

A more efficient algorithm exists:

• Sort A
• Build an array of ranks from the elements of B.
  • For example for [5, 6, 4] the ranks would be [1, 2, 0]
• Map the ranks to values in sorted A

The smallest part of this algorithm is the sorting of arrays (of A, and when building the ranks). That gives an improved time complexity of \$O(n \log n)\$.

// returns an array where each value is the rank
// of the corresponding value in nums.
// for example: given [1, 8, 4, 9] -> [0, 2, 1, 3]
function buildRanks(nums) {
  // build array of indexes ("identity map": 0 -> 0, 1 -> 1, ...)
  const indexes = Array(nums.length);
  for (let i = 0; i < nums.length; i++) {
    indexes[i] = i;
  }

  // reorder the indexes to match the ordering of values in nums
  indexes.sort((a, b) => nums[a] - nums[b]);

  // build array of ranks, using sorted indexes
  const ranks = Array(nums.length);
  for (let rank = 0; rank < nums.length; rank++) {
    ranks[indexes[rank]] = rank;
  }
  return ranks;
}

function sortTeam(A, B) {
  // using [...A] to avoid mutating A itself
  const sortedA = [...A].sort((a, b) => a - b);

  // map ranks of B to sorted values of A
  return buildRanks(B)
    .map(rank => sortedA[rank]);
}

Answer 3

Several things.

Firstly, the code as it is throws a syntax error. You can fix this by removing the =>.

Secondly, since you're not using the variables i and j except to index into the lists a and b, you can just use a for-of loop:

function sortTeam(a, b){
    let result = [];
    const asort = a.slice().sort((a,b) => a - b);
    for (let bi of b){
        for (let aj of asort){
            if (!result.includes(aj) && aj > bi){
                result.push(aj);
                break;
            }
        }
    }
    console.log('result', result);
    return result;
}

Finally, you probably want to use more descriptive variable names (although (a,b) => a - b is fine), and you don't need the console.log call - if you want to log the result, log the return value of the function: If you're calling this function thousands of times, you don't want to fill up the screen with its results.

function sortTeam(teamA, teamB){
    let result = [];
    const sortedTeamA = teamA.slice().sort((a,b) => a - b);
    for (let playerB of teamB){
        for (let playerA of sortedTeamA){
            if (!result.includes(playerA) && playerA > playerB){
                result.push(playerA);
                break;
            }
        }
    }
    return result;
}