Count Number of Teams

medium array counting

Problem

There are n soldiers standing in a row, each with a distinct rating. A team is any three soldiers picked at positions i < j < k whose ratings read strictly increasing (rating[i] < rating[j] < rating[k]) or strictly decreasing (rating[i] > rating[j] > rating[k]) from left to right. Count how many different teams can be formed — the same soldier may belong to several teams.

Inputrating = [2, 5, 3, 4, 1]

Output3

The valid teams are (2,3,4), (5,4,1) and (5,3,1); each one is strictly increasing or strictly decreasing.

rating (comma-separated, distinct integers)

def num_teams(rating):
    n = len(rating)
    teams = 0
    for j in range(1, n - 1):
        less_left = greater_left = 0
        less_right = greater_right = 0
        for i in range(j):
            if rating[i] < rating[j]:
                less_left += 1
            else:
                greater_left += 1
        for k in range(j + 1, n):
            if rating[k] > rating[j]:
                greater_right += 1
            else:
                less_right += 1
        teams += less_left * greater_right
        teams += greater_left * less_right
    return teams

function numTeams(rating) {
  const n = rating.length;
  let teams = 0;
  for (let j = 1; j < n - 1; j++) {
    let lessLeft = 0, greaterLeft = 0;
    let lessRight = 0, greaterRight = 0;
    for (let i = 0; i < j; i++) {
      if (rating[i] < rating[j]) lessLeft++;
      else greaterLeft++;
    }
    for (let k = j + 1; k < n; k++) {
      if (rating[k] > rating[j]) greaterRight++;
      else lessRight++;
    }
    teams += lessLeft * greaterRight;
    teams += greaterLeft * lessRight;
  }
  return teams;
}

int numTeams(int[] rating) {
    int n = rating.length, teams = 0;
    for (int j = 1; j < n - 1; j++) {
        int lessLeft = 0, greaterLeft = 0;
        int lessRight = 0, greaterRight = 0;
        for (int i = 0; i < j; i++) {
            if (rating[i] < rating[j]) lessLeft++;
            else greaterLeft++;
        }
        for (int k = j + 1; k < n; k++) {
            if (rating[k] > rating[j]) greaterRight++;
            else lessRight++;
        }
        teams += lessLeft * greaterRight;
        teams += greaterLeft * lessRight;
    }
    return teams;
}

int numTeams(vector<int>& rating) {
    int n = rating.size(), teams = 0;
    for (int j = 1; j < n - 1; j++) {
        int lessLeft = 0, greaterLeft = 0;
        int lessRight = 0, greaterRight = 0;
        for (int i = 0; i < j; i++) {
            if (rating[i] < rating[j]) lessLeft++;
            else greaterLeft++;
        }
        for (int k = j + 1; k < n; k++) {
            if (rating[k] > rating[j]) greaterRight++;
            else lessRight++;
        }
        teams += lessLeft * greaterRight;
        teams += greaterLeft * lessRight;
    }
    return teams;
}

Explanation

Checking every triple (i, j, k) directly costs O(n³). The key insight: every team has exactly one middle soldier, so instead of enumerating triples we can fix the middle j and count how many valid teams it anchors — picking one compatible soldier from each side is a simple multiplication.

For each middle index j we make one pass over the array and record four counters: lessLeft and greaterLeft (soldiers before j rating below or above rating[j]), and lessRight and greaterRight (the same for soldiers after j). Because all ratings are distinct, every soldier falls into exactly one bucket.

An increasing team through j needs a smaller rating on the left and a larger one on the right, and any such pair works, giving lessLeft × greaterRight teams. Symmetrically, decreasing teams contribute greaterLeft × lessRight. Since each team is counted only at its unique middle, nothing is double counted.

Walking through rating = [2, 5, 3, 4, 1]: for j = 1 (rating 5) the products are 1×0 + 0×3 = 0; for j = 2 (rating 3) they are 1×1 + 1×1 = 2, finding (2,3,4) and (5,3,1); for j = 3 (rating 4) they are 2×0 + 1×1 = 1, finding (5,4,1). The total is 0 + 2 + 1 = 3.

Each of the n − 2 middle choices scans the other n − 1 elements once, so the running time is O(n²) — a big drop from the O(n³) brute force. We only keep a handful of counters, so extra space is O(1). (A Fenwick tree can push this to O(n log n), but for the given constraints the quadratic count is the clean answer.)

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