1395. Count Number of Teams

[mah-shamim]

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

Example 4:

• Input: rating = [2173,478,1128,2138,785,159,819,2747,557,2422,2092,1105,1374,2450,1574,951,1290,1590,1929,1605,1646,2791,2701,2911,971,2066,493,1593,1537,257,205,1109,79,470,1790,221,180,1891,250,1798,75,2778,2302,1299,923,355,2399,2536,2628,2805,1046,1555,2178,2722,1843,754,1908,610,2933,613,2047,2296,2820,1815,2997,431,1320,11,1387,227,913,2530,1680,2136,2589,2027,2003,2699,1271,1831,666,1872,1268,62,399,1665,1508,2228,2079,1418,1937,2686,1429,58,1696,161,2476,1950,857,699,2792,1353,2901,2923,330,99,1711,2546,2405,1340,2456,664,2584,2741,60,488,2406,1988,1827,1514,1708,2043,513,789,1284,2132,1600,646,2660,552,2139,507,1256,374,1655,1899,2295,288,2606,1874,776,2361,1958,751,2759,386,438,644,1954,2788,2081,832,2230,2602,2222,919,2905,694,2793,2562,2867,1169,1732,1381,2462,1230,284,1624,2496,748,2107,385,1064,1267,2058,499,2203,215,88,585,525,1136,309,1851,2085,109,2809,517,409,2419,2384,2308,2292,1994,2943,1294,1781,1862,2841,2096,662,2014,2426,2821,2400,113,129,2193,2865,618,121,1038,1782,2468,2861,234,249,2967,1533,607,1453,1465,477,471,1778,2143,1050,1728,1332,1967,73,1698,626,1449,2833,2447,917,2500,1920,673,1234,1420,1659,880,584,2023,1281,1544,1380,2019,2131,1018,152,2268,2052,2372,1017,2807,1424,633,1726,523,373,2850,1025,2371,1405,2252,996,895,1475,1886,2002,1720,1826,381,1835,1666,2879,2255,182,2641,2680,2920,1336,2061,1969,394,858,480,2322,766,1176,2995,1691,681,2595,1758,745,2492,1212,2776,1177,1027,448,2866,2423,2156,701,1184,2294,612,1963,2928,2851,875,949,814,244,2930,2306,2515,1266,522,830,2364,2209,1168,1372,686,325,354,511,1860,2828,1504,2176,1189,2694,1838,392,594,1091,1183,368,862,1457,2191,1096,410,177,274,2033,5,1697,1573,504,2725,2859,2401,2122,1118,813,936,455,1115,671,690,1067,144,155,2060,1998,2242,1978,566,624,518,2086,76,1526,2219,2618,2180,2880,1301,166,2153,2202,944,2346,196,720,2529,1945,2772,1441,2715,2366,1578,838,464,194,1645,1020,1042,2474,1060,1314,1207,1245,890,2057,643,2540,2094,1529,932,2563,545,1153,803,1742,1102,2351,370,1369,1973,1837,2250,2121,178,266,521,2259,1850,2964,1964,726,1743,2410,716,2118,1265,2542,878,1924,532,812,2487,1417,2262,321,920,2217,497,1875,555,2662,898,1404,2408,253,65,1916,2486,445,797,1765,1376,1470,2181,2856,2554,2045,1415,2858,1842,248,1810,596,453,1816,1802,1517,397,760,2324,1930,2522,2216,736,297,2755,107,2110,2965,755,1261,2415,1395,1016,809,2913,1779,55,2297,1637,2691,67,1983,185,2080,656,1014,1795,2220,1024,2658,1610,361,2800,2448,1174,2425,1479,256,2605,2320,1832,1991,588,1019,2317,278,727,242,2586,1431,371,2293,1371,1445,2864,2548,773,1615,1868,582,2692,589,1489,2009,1905,2831,2084,2104,138,1580,446,389,847,2028,1262,68,889,1767,907,989,1152,203,2089,2328,417,1248,2843,1451,1972,1409,1519,2455,2383,943,683,108,2395,1773,2356,2337,839,1717,1777,1757,2115,2925,1430,1933,1005,2736,2958,1295,307,1028,597,739,51,157,2375,933,2385,292,905,280,893,1315,2323,1562,2435,1746,2090,985,420,2742,2949,304,842,1487,520,1556,2862,684,711,271,1283,2166,2545,425,429,1497]
• Output: 14510756

Constraints:

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

Hint:

1. BruteForce, check all possibilities.

[mah-shamim]

To solve this problem, we can follow these steps:

Let's implement this solution in PHP: 1395. Count Number of Teams

<?php
// Example usage:
$rating1 = [2, 5, 3, 4, 1];
$rating2 = [2, 1, 3];
$rating3 = [1, 2, 3, 4];
$rating4 = [2173, 478, 1128, 2138, 785, 159, 819, 2747, 557, 2422, 2092, 1105, 1374, 2450, 1574, 951, 1290, 1590, 1929, 1605, 1646, 2791, 2701, 2911, 971, 2066, 493, 1593, 1537, 257, 205, 1109, 79, 470, 1790, 221, 180, 1891, 250, 1798, 75, 2778, 2302, 1299, 923, 355, 2399, 2536, 2628, 2805, 1046, 1555, 2178, 2722, 1843, 754, 1908, 610, 2933, 613, 2047, 2296, 2820, 1815, 2997, 431, 1320, 11, 1387, 227, 913, 2530, 1680, 2136, 2589, 2027, 2003, 2699, 1271, 1831, 666, 1872, 1268, 62, 399, 1665, 1508, 2228, 2079, 1418, 1937, 2686, 1429, 58, 1696, 161, 2476, 1950, 857, 699, 2792, 1353, 2901, 2923, 330, 99, 1711, 2546, 2405, 1340, 2456, 664, 2584, 2741, 60, 488, 2406, 1988, 1827, 1514, 1708, 2043, 513, 789, 1284, 2132, 1600, 646, 2660, 552, 2139, 507, 1256, 374, 1655, 1899, 2295, 288, 2606, 1874, 776, 2361, 1958, 751, 2759, 386, 438, 644, 1954, 2788, 2081, 832, 2230, 2602, 2222, 919, 2905, 694, 2793, 2562, 2867, 1169, 1732, 1381, 2462, 1230, 284, 1624, 2496, 748, 2107, 385, 1064, 1267, 2058, 499, 2203, 215, 88, 585, 525, 1136, 309, 1851, 2085, 109, 2809, 517, 409, 2419, 2384, 2308, 2292, 1994, 2943, 1294, 1781, 1862, 2841, 2096, 662, 2014, 2426, 2821, 2400, 113, 129, 2193, 2865, 618, 121, 1038, 1782, 2468, 2861, 234, 249, 2967, 1533, 607, 1453, 1465, 477, 471, 1778, 2143, 1050, 1728, 1332, 1967, 73, 1698, 626, 1449, 2833, 2447, 917, 2500, 1920, 673, 1234, 1420, 1659, 880, 584, 2023, 1281, 1544, 1380, 2019, 2131, 1018, 152, 2268, 2052, 2372, 1017, 2807, 1424, 633, 1726, 523, 373, 2850, 1025, 2371, 1405, 2252, 996, 895, 1475, 1886, 2002, 1720, 1826, 381, 1835, 1666, 2879, 2255, 182, 2641, 2680, 2920, 1336, 2061, 1969, 394, 858, 480, 2322, 766, 1176, 2995, 1691, 681, 2595, 1758, 745, 2492, 1212, 2776, 1177, 1027, 448, 2866, 2423, 2156, 701, 1184, 2294, 612, 1963, 2928, 2851, 875, 949, 814, 244, 2930, 2306, 2515, 1266, 522, 830, 2364, 2209, 1168, 1372, 686, 325, 354, 511, 1860, 2828, 1504, 2176, 1189, 2694, 1838, 392, 594, 1091, 1183, 368, 862, 1457, 2191, 1096, 410, 177, 274, 2033, 5, 1697, 1573, 504, 2725, 2859, 2401, 2122, 1118, 813, 936, 455, 1115, 671, 690, 1067, 144, 155, 2060, 1998, 2242, 1978, 566, 624, 518, 2086, 76, 1526, 2219, 2618, 2180, 2880, 1301, 166, 2153, 2202, 944, 2346, 196, 720, 2529, 1945, 2772, 1441, 2715, 2366, 1578, 838, 464, 194, 1645, 1020, 1042, 2474, 1060, 1314, 1207, 1245, 890, 2057, 643, 2540, 2094, 1529, 932, 2563, 545, 1153, 803, 1742, 1102, 2351, 370, 1369, 1973, 1837, 2250, 2121, 178, 266, 521, 2259, 1850, 2964, 1964, 726, 1743, 2410, 716, 2118, 1265, 2542, 878, 1924, 532, 812, 2487, 1417, 2262, 321, 920, 2217, 497, 1875, 555, 2662, 898, 1404, 2408, 253, 65, 1916, 2486, 445, 797, 1765, 1376, 1470, 2181, 2856, 2554, 2045, 1415, 2858, 1842, 248, 1810, 596, 453, 1816, 1802, 1517, 397, 760, 2324, 1930, 2522, 2216, 736, 297, 2755, 107, 2110, 2965, 755, 1261, 2415, 1395, 1016, 809, 2913, 1779, 55, 2297, 1637, 2691, 67, 1983, 185, 2080, 656, 1014, 1795, 2220, 1024, 2658, 1610, 361, 2800, 2448, 1174, 2425, 1479, 256, 2605, 2320, 1832, 1991, 588, 1019, 2317, 278, 727, 242, 2586, 1431, 371, 2293, 1371, 1445, 2864, 2548, 773, 1615, 1868, 582, 2692, 589, 1489, 2009, 1905, 2831, 2084, 2104, 138, 1580, 446, 389, 847, 2028, 1262, 68, 889, 1767, 907, 989, 1152, 203, 2089, 2328, 417, 1248, 2843, 1451, 1972, 1409, 1519, 2455, 2383, 943, 683, 108, 2395, 1773, 2356, 2337, 839, 1717, 1777, 1757, 2115, 2925, 1430, 1933, 1005, 2736, 2958, 1295, 307, 1028, 597, 739, 51, 157, 2375, 933, 2385, 292, 905, 280, 893, 1315, 2323, 1562, 2435, 1746, 2090, 985, 420, 2742, 2949, 304, 842, 1487, 520, 1556, 2862, 684, 711, 271, 1283, 2166, 2545, 425, 429, 1497];

// Print results
echo numTeams($rating1) . "\n"; // Output: 3
echo numTeams($rating2) . "\n"; // Output: 0
echo numTeams($rating3) . "\n"; // Output: 4
echo numTeams($rating4) . "\n"; // Output: 14510756

?>

Explanation:

• The code iterates over each soldier (position j) and counts how many soldiers on its left are less than and greater than it (leftLess and leftMore).
• Similarly, it counts how many soldiers on its right are less than and greater than it (rightLess and rightMore).
• A valid team can be formed in two ways:
  1. Soldiers on the left are less and soldiers on the right are greater (leftLess * rightMore).
  2. Soldiers on the left are greater and soldiers on the right are less (leftMore * rightLess).
• The total number of teams is accumulated in the $count variable.

[kovatz]

good answer