1395. Count Number of Teams

Description

There are n soldiers standing in a line. Each soldier is assigned a unique rating value.

You have to form a team of 3 soldiers amongst them under the following rules:

• Choose 3 soldiers with index (i, j, k) with rating (rating[i], rating[j], rating[k]).
• A team is valid if: (rating[i] < rating[j] < rating[k]) or (rating[i] > rating[j] > rating[k]) where (0 <= i < j < k < n).

Return the number of teams you can form given the conditions. (soldiers can be part of multiple teams).

 

Example 1:

Input: rating = [2,5,3,4,1]
Output: 3
Explanation: We can form three teams given the conditions. (2,3,4), (5,4,1), (5,3,1). 

Example 2:

Input: rating = [2,1,3]
Output: 0
Explanation: We can't form any team given the conditions.

Example 3:

Input: rating = [1,2,3,4]
Output: 4

 

Constraints:

• n == rating.length
• 3 <= n <= 1000
• 1 <= rating[i] <= 105
• All the integers in rating are unique.

 

Solutions

Solution: Dynamic Programming

• Time complexity: O(n²)
• Space complexity: O(1)

 

JavaScript

/**
 * @param {number[]} rating
 * @return {number}
 */
const numTeams = function (rating) {
  let result = 0;

  for (let index = 1; index < rating.length - 1; index++) {
    const rate = rating[index];
    let leftBigger = (leftSmaller = 0);
    let rightBigger = (rightSmaller = 0);

    for (let left = 0; left < index; left++) {
      rate < rating[left] ? (leftBigger += 1) : (leftSmaller += 1);
    }
    for (let right = index + 1; right < rating.length; right++) {
      rate < rating[right] ? (rightBigger += 1) : (rightSmaller += 1);
    }
    result += leftBigger * rightSmaller + leftSmaller * rightBigger;
  }
  return result;
};

 

Solution: Binary Indexed Tree

• Time complexity: O(nlogn)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {number[]} rating
 * @return {number}
 */
const numTeams = function (rating) {
  const n = rating.length;
  const sortedRating = [...rating].sort((a, b) => a - b);
  const bit = new Array(n + 2).fill(0);

  const getIndex = value => {
    let left = 0;
    let right = n - 1;

    while (left < right) {
      const mid = Math.floor((left + right) / 2);

      sortedRating[mid] >= value ? (right = mid) : (left = mid + 1);
    }
    return left;
  };

  const updateBit = index => {
    while (index < bit.length) {
      bit[index] += 1;
      index += index & -index;
    }
  };

  const queryBit = index => {
    let count = 0;

    while (index > 0) {
      count += bit[index];
      index -= index & -index;
    }
    return count;
  };
  let result = 0;

  for (const value of rating) {
    const index = getIndex(value);
    const leftSmallerCount = queryBit(index);
    const leftBiggerCount = queryBit(n) - queryBit(index + 1);
    const rightSmallerCount = index - leftSmallerCount;
    const rightBiggerCount = n - index - 1 - leftBiggerCount;

    updateBit(index + 1);
    result += leftSmallerCount * rightBiggerCount + leftBiggerCount * rightSmallerCount;
  }
  return result;
};