This content originally appeared on DEV Community and was authored by DEV Community
Intro: I am a former accountant turned software engineer graduated from coding bootcamp. Algorithms and Data Structure is an unavoidable part of interviews for most of the tech companies now. And one of my friends told me that you need to solve a medium leetcode problem under 60 seconds in order to get into the top tech companies.So I thought I'd start learning how to do it while job searching.
Since I have no clue on how to solve any of the problems (even the easy ones), I thought there is no point for me to waste hours and can't get it figured out. Here is my approach:
- Pick a leetcode problem randomly or Online Assessment from targeted companies.
- Study 1-2 solutions from Youtube or LeetCode discussion section. One brute force solution, another one more optimal.
- Write a blog post with detailed explanation and do a verbal walk through to help understand the solutions better.
- Code out the solution in LeetCode without looking at the solutions
- Combat the forgetting curve: Re-do the question for the next three days. And come back regularly to revisit the problem.
1395. Count Number of Teams
Difficulty: Medium Language: JavaScript
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.length3 <= n <= 10001 <= rating[i] <= 105- All the integers in
ratingare unique.
Solution:
Key to this solution is the number of teams that meets the condition can be calculated by finding the middle rating if the team. The count of ratings smaller than the middle rating multiplies the count of ratings greater than middle rating will give us all posible combination that meets the condition. For example, given rating [1,2,3,4], there are 4 output that meets the conditon: [1,2,3],[1,2,4],[1,3,4],[2,3,4]. When 2 is the middle rating, there are 2 numbers ('3' & '4') greater and 1 number ('1') smaller than the middle rating, 2*1 = 2 combinations that meet th econdition. And when 3 is the middle number, there are also 2 combinations. Total combination is 2 + 2 = 4. Since 0 <= i < j < k < n, the middle number can only be 2 and 3. This problem allows the combination to be ascending and descending order, so we will consider these two situation when we write code.
var numTeams = function(rating) {
let solution = 0;
//initialize solution as 0
for (let i = 1; i < rating.length - 1; i++){
//Loop (ntoe 1) through 'rating' array and keep count of numbers
//that are greater or smaller than raiting[i]. Because we are
//locating the middle ratings, the iteration will start at 1 and
//end at the second last number (rating.length-1)(ntoe 2) in the
//array.
let ascSmaller = 0,
ascGreater = 0,
descSmaller = 0,
descGreater = 0;
//Declare variables and set initial value as 0, these counts are
//used to calculate the solution
for (let j = i+1; j < rating.length; j++){
if (rating[j] > rating[i]) ascGreater++
if (rating[j] < rating[i]) descSmaller++
}
//starting from the number next to middle number and end at last
//element of the array. If the numbers are greater than middle
//number increase (note 4) count for 'ascGreater' and
//'descSmaller' respectively.
for (let j = i-1; j >= 0; j--){
if (rating[j] > rating[i]) descGreater++
if (rating[j] < rating[i]) ascSmaller++
}
//starting from the number prior to middle number and end at first
//element of the array. If the numbers are smaller than middle
//number increase (note 4) count for 'descGreater' and
//'ascSmaller' respectively.
solution += ascSmaller*ascGreater + descSmaller*descGreater
//as mentioned in the explanation above, this problem allows the
//combination to be ascending and descending order. Hence, we
//combine (note 3) the total output for each order together.
}
return solution
};
Time and Space Complexity
- Time: O(n^2)
- Space: ?
References:
LeetCode Problem Link
Note 1: For Loop
Note 2: Array.length
Note 3: Addition assignment (+=)
Note 4: Increment (++)
Blog Cover Image Credit
This content originally appeared on DEV Community and was authored by DEV Community
DEV Community | Sciencx (2022-03-06T00:54:47+00:00) Day 24 of Studying LeetCode Solution until I Can Solve One on My Own: Problem#1395. Count Number of Teams(Medium/JavaScript). Retrieved from https://www.scien.cx/2022/03/06/day-24-of-studying-leetcode-solution-until-i-can-solve-one-on-my-own-problem1395-count-number-of-teamsmedium-javascript/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.