LC-1395 Medium LeetCode

1395. Count Number of Teams

Array Dynamic Programming Binary Indexed Tree Segment Tree

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 70% Topics: Array, Dynamic Programming, Binary Indexed Tree, Segment Tree

Reading material

Arrays & Hashing 12 min 1-D Dynamic Programming 16 min Segment & Fenwick Trees 16 min

Reference solution (spoiler · python)

# Time:  O(n^2)
# Space: O(1)

class Solution(object):
    def numTeams(self, rating):
        """
        :type rating: List[int]
        :rtype: int
        """
        result = 0
        for i in xrange(1, len(rating)-1):
            less, greater = [0]*2, [0]*2
            for j in xrange(len(rating)):
                if rating[i] > rating[j]:
                    less[i < j] += 1
                if rating[i] < rating[j]:
                    greater[i < j] += 1
            result += less[0]*greater[1] + greater[0]*less[1]
        return result

Solution from kamyu104/LeetCode-Solutions · MIT