LeetCode 1431. Kids With the Greatest Number of Candies

September 11, 2020

We can do this in $O(n)$ time with:

One pass to find the max.
One pass to find all kids that have at least $max - extraCandies$ candies.

Can we do it in a single pass? I don't think so. There's no way for us to know the max before we do at least 1 pass. Any crazy stuff we do to keep it to a single pass stil wouldn't be able to compute the final output true/false without the max. Building the final output boolean array is unavoidable.

from typing import List
import unittest

class Test(unittest.TestCase):

    def setUp(self):
        self.s = Solution()

    def test_examples(self):
        self.assertEqual(self.s.kidsWithCandies([2,3,5,1,3], 3), [True,True,True,False,True])
        self.assertEqual(self.s.kidsWithCandies([4,2,1,1,2], 1), [True,False,False,False,False])
        self.assertEqual(self.s.kidsWithCandies([12,1,12], 10), [True,False,True])

    def test_empty(self):
        self.assertEqual(self.s.kidsWithCandies([], 50), [])

    def test_one(self):
        for i in range(10):
            self.assertEqual(self.s.kidsWithCandies([i], i), [True])

    def test_all_equal(self):
        self.assertEqual(self.s.kidsWithCandies([1,1,1,1,1], 27), [True,True,True,True,True])

class Solution:
    
    def kidsWithCandies(self, candies: List[int], extraCandies: int) -> List[bool]:
        if not candies:
            return []
        m = candies[0]
        for c in candies:
            if c > m:
                m = c
        return [c + extraCandies >= m for c in candies]

if __name__ == "__main__":
    unittest.main()