We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Implementation
  4. Non-Divisible Subset
  5. Discussions

Non-Divisible Subset

  • jtravegordillo
     + 0 comments

    Python O(n + m) solution. This is better than using binary search tree, which are usually O(m*log n)

    def climbingLeaderboard(ranked: list[int], player: list[int]) -> list[int]:
    # Write your code here
    ranked = [float("inf")] + ranked
    el_ranked_dict = {ranked[0]: 0}
    for i in range(1, len(ranked)):
        if ranked[i] == ranked[i - 1]:
            el_ranked_dict[ranked[i]] = el_ranked_dict[ranked[i - 1]]
        else:
            el_ranked_dict[ranked[i]] = el_ranked_dict[ranked[i - 1]] + 1
    last_index = len(ranked)
    result = []
    for score in player:
        for i in range(last_index, 0, -1):
            el = ranked[i - 1]
            if el > score:
                last_index = i
                result.append(el_ranked_dict[el] + 1)
                break
    return result