DEV Community

Cover image for 1395. Count Number of Teams
MD ARIFUL HAQUE
MD ARIFUL HAQUE

Posted on

2

1395. Count Number of Teams

1395. Count Number of Teams

Medium

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.

Solution:

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

?>
Enter fullscreen mode Exit fullscreen mode

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.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

Image of Docusign

🛠️ Bring your solution into Docusign. Reach over 1.6M customers.

Docusign is now extensible. Overcome challenges with disconnected products and inaccessible data by bringing your solutions into Docusign and publishing to 1.6M customers in the App Center.

Learn more

Top comments (0)

AWS Security LIVE!

Tune in for AWS Security LIVE!

Join AWS Security LIVE! for expert insights and actionable tips to protect your organization and keep security teams prepared.

Learn More

👋 Kindness is contagious

Discover a treasure trove of wisdom within this insightful piece, highly respected in the nurturing DEV Community enviroment. Developers, whether novice or expert, are encouraged to participate and add to our shared knowledge basin.

A simple "thank you" can illuminate someone's day. Express your appreciation in the comments section!

On DEV, sharing ideas smoothens our journey and strengthens our community ties. Learn something useful? Offering a quick thanks to the author is deeply appreciated.

Okay