Skip to main content
Computer Science

Return to Answer

Better and more consistent variable name.
Source Link
John L.
John L.
  • 39.1k
  • 4
  • 34
  • 91

Here is a cleaner and better way to solve the problem.

# Return the smallest index where the element is bigger than `A[start_index]`.
# If `len(A)` is returned, no element is bigger than `A[start_index]`.
def next_bigger_element(start_index, A):
    lo, hi = start_index, len(A)
    while lo + 1 < hi:
        mid = (lo + hi) // 2
        if A[mid] == A[start_index]:
            lo = mid
        else:
            hi = mid
    return hi


def distinct_elements_at_least(k, A):
    if len(A) == 0:
        return k <= 0
    cur_indexindex = 0
    count = 1
    # keep finding the next bigger element until `k` elements have
    # been found or we have reached the end of the array.
    while count < k and A[cur_index]A[index] != A[-1]:
        cur_indexindex = next_bigger_element(cur_indexindex, A)
        count += 1
    return count >= k

To find whether A contains at least 4 distinct elements, just call distinct_elements_at_least(4, A).

This program works correctly for any given number k. For example, it can be used to check whether A has 0 element or whether A has 7 distinct elements. For any fixed k, it works in $O(\log n)$ time as at most k binary searches on an interval of size at most n are done.

If you do not mind import bisect, you may prefer the following shorter code, since method next_bigger_element is no longer needed.

from bisect import bisect_right

def distinct_elements_at_least(k, A):
    if len(A) == 0:
        return k <= 0
    curindex = 0
    count = 0
    while curindex < len(A) and count < k:
        count += 1
        curindex = bisect_right(A, A[cur]A[index], curindex + 1)
    return count >= k

Here is a cleaner and better way to solve the problem.

# Return the smallest index where the element is bigger than `A[start_index]`.
# If `len(A)` is returned, no element is bigger than `A[start_index]`.
def next_bigger_element(start_index, A):
    lo, hi = start_index, len(A)
    while lo + 1 < hi:
        mid = (lo + hi) // 2
        if A[mid] == A[start_index]:
            lo = mid
        else:
            hi = mid
    return hi


def distinct_elements_at_least(k, A):
    if len(A) == 0:
        return k <= 0
    cur_index = 0
    count = 1
    # keep finding the next bigger element until `k` elements have
    # been found or we have reached the end of the array.
    while count < k and A[cur_index] != A[-1]:
        cur_index = next_bigger_element(cur_index, A)
        count += 1
    return count >= k

To find whether A contains at least 4 distinct elements, just call distinct_elements_at_least(4, A).

This program works correctly for any given number k. For example, it can be used to check whether A has 0 element or whether A has 7 distinct elements. For any fixed k, it works in $O(\log n)$ time as at most k binary searches on an interval of size at most n are done.

If you do not mind import bisect, you may prefer the following shorter code, since method next_bigger_element is no longer needed.

from bisect import bisect_right

def distinct_elements_at_least(k, A):
    if len(A) == 0:
        return k <= 0
    cur = 0
    count = 0
    while cur < len(A) and count < k:
        count += 1
        cur = bisect_right(A, A[cur], cur + 1)
    return count >= k

Here is a cleaner and better way to solve the problem.

# Return the smallest index where the element is bigger than `A[start_index]`.
# If `len(A)` is returned, no element is bigger than `A[start_index]`.
def next_bigger_element(start_index, A):
    lo, hi = start_index, len(A)
    while lo + 1 < hi:
        mid = (lo + hi) // 2
        if A[mid] == A[start_index]:
            lo = mid
        else:
            hi = mid
    return hi


def distinct_elements_at_least(k, A):
    if len(A) == 0:
        return k <= 0
    index = 0
    count = 1
    # keep finding the next bigger element until `k` elements have
    # been found or we have reached the end of the array.
    while count < k and A[index] != A[-1]:
        index = next_bigger_element(index, A)
        count += 1
    return count >= k

To find whether A contains at least 4 distinct elements, just call distinct_elements_at_least(4, A).

This program works correctly for any given number k. For example, it can be used to check whether A has 0 element or whether A has 7 distinct elements. For any fixed k, it works in $O(\log n)$ time as at most k binary searches on an interval of size at most n are done.

If you do not mind import bisect, you may prefer the following shorter code, since method next_bigger_element is no longer needed.

from bisect import bisect_right

def distinct_elements_at_least(k, A):
    if len(A) == 0:
        return k <= 0
    index = 0
    count = 0
    while index < len(A) and count < k:
        count += 1
        index = bisect_right(A, A[index], index + 1)
    return count >= k
Fixed a typo.
Source Link
John L.
John L.
  • 39.1k
  • 4
  • 34
  • 91

Here is a cleaner and better way to solve the problem.

# Return the smallest index where the element is bigger than `A[start_index]`.
# If `len(A)` is returned, no element is bigger than `A[start_index]`.
def next_bigger_element(start_index, A):
    lo, hi = start_index, len(A)
    while lo + 1 < hi:
        mid = (lo + hi) // 2
        if A[mid] == A[start_index]:
            lo = mid
        else:
            hi = mid
    return hi


def distinct_elements_at_least(k, A):
    if len(A) == 0:
        return k <= 0
    cur_index = 0
    count = 1
    # keep finding the next bigger element as long as less thanuntil `k` distinctelements have
    # elements has been found andor we have reached the end of the array has not been reached.
    while count < k and A[cur_index] != A[-1]:
        cur_index = next_bigger_element(cur_index, A)
        count += 1
    return count >= k

To find whether A contains at least 4 distinct elements, just call distinct_elements_at_least(4, A).

This program works correctly for any given number k. For example, it can be used to check whether A has 0 element or whether A has 7 distinct elements. For any fixed k, it works in $O(\log n)$ time as desiredat most k binary searches on an interval of size at most n are done.

If you do not mind import bisect, you may prefer the following shorter code, since method next_bigger_element is no longer needed.

from bisect import bisect_right

def distinct_elements_at_least(k, A):
    if len(A) == 0:
        return k <= 0
    cur = 0
    count = 0
    while cur < len(A) and count < k:
        count += 1
        cur = bisect_right(A, A[cur], cur + 1)
    return count >= k

Here is a cleaner and better way to solve the problem.

# Return the smallest index where the element is bigger than `A[start_index]`.
# If `len(A)` is returned, no element is bigger than `A[start_index]`.
def next_bigger_element(start_index, A):
    lo, hi = start_index, len(A)
    while lo + 1 < hi:
        mid = (lo + hi) // 2
        if A[mid] == A[start_index]:
            lo = mid
        else:
            hi = mid
    return hi


def distinct_elements_at_least(k, A):
    if len(A) == 0:
        return k <= 0
    cur_index = 0
    count = 1
    # keep finding the next bigger element as long as less than `k` distinct
    # elements has been found and the end of the array has not been reached.
    while count < k and A[cur_index] != A[-1]:
        cur_index = next_bigger_element(cur_index, A)
        count += 1
    return count >= k

To find whether A contains at least 4 distinct elements, just call distinct_elements_at_least(4, A).

This program works correctly for any given number k. For example, it can be used to check whether A has 0 element or whether A has 7 distinct elements. For any fixed k, it works in $O(\log n)$ as desired.

If you do not mind import bisect, you may prefer the following shorter code, since method next_bigger_element is no longer needed.

from bisect import bisect_right

def distinct_elements_at_least(k, A):
    if len(A) == 0:
        return k <= 0
    cur = 0
    count = 0
    while cur < len(A) and count < k:
        count += 1
        cur = bisect_right(A, A[cur], cur + 1)
    return count >= k

Here is a cleaner and better way to solve the problem.

# Return the smallest index where the element is bigger than `A[start_index]`.
# If `len(A)` is returned, no element is bigger than `A[start_index]`.
def next_bigger_element(start_index, A):
    lo, hi = start_index, len(A)
    while lo + 1 < hi:
        mid = (lo + hi) // 2
        if A[mid] == A[start_index]:
            lo = mid
        else:
            hi = mid
    return hi


def distinct_elements_at_least(k, A):
    if len(A) == 0:
        return k <= 0
    cur_index = 0
    count = 1
    # keep finding the next bigger element until `k` elements have
    # been found or we have reached the end of the array.
    while count < k and A[cur_index] != A[-1]:
        cur_index = next_bigger_element(cur_index, A)
        count += 1
    return count >= k

To find whether A contains at least 4 distinct elements, just call distinct_elements_at_least(4, A).

This program works correctly for any given number k. For example, it can be used to check whether A has 0 element or whether A has 7 distinct elements. For any fixed k, it works in $O(\log n)$ time as at most k binary searches on an interval of size at most n are done.

If you do not mind import bisect, you may prefer the following shorter code, since method next_bigger_element is no longer needed.

from bisect import bisect_right

def distinct_elements_at_least(k, A):
    if len(A) == 0:
        return k <= 0
    cur = 0
    count = 0
    while cur < len(A) and count < k:
        count += 1
        cur = bisect_right(A, A[cur], cur + 1)
    return count >= k
Shave off one round of binary-search. More reading-friendly method signatures. Better implementation by bisect_right.
Source Link
John L.
John L.
  • 39.1k
  • 4
  • 34
  • 91
# Return the smallest index where the element is bigger than A[cur]`A[start_index]`.
# ifIf len`len(A)` is returned, no element is bigger than A[cur]`A[start_index]`.
def next_bigger_element(Astart_index, curA):
    lo, hi = curstart_index, len(A)
    while lo + 1 < hi:
        mid = (lo + hi) // 2
        if A[mid] == A[cur]A[start_index]:
            lo = mid
        else:
            hi = mid
    return hi 


def distinct_elements_at_least(Ak, kA):
    curif len(A) == 0:
        return k <= 0
    cur_index = 0
    count = 01
    while# curkeep !=finding len(A)the andnext countbigger <element k:as long as less than `k` distinct
    # elements has been found and the end of the array has not been reached.
    while count +=< 1k and A[cur_index] != A[-1]:
        curcur_index = next_bigger_element(Acur_index, curA)
        count += 1
    return count ==>= k

To find whether A contains at least 4 distinct elements, just call distinct_elements_at_least(A4, 4A).

WeThis program works correctly for any given number k. For example, it can use thisbe used to solve all similar problems, such ascheck whether A contains at least 2 distinct elements orhas 0 element or whether A contains 777has 7 distinct elements. The method works correctly even if you want to check whetherFor any fixed Ak contains at least 0 element or whether, it works in A contains at least 1 element!$O(\log n)$ as desired.

If you do not mind import bisect, you may likeprefer the following even shorter method, in the cases where, for examplecode, elements insince method Anext_bigger_element are integersis no longer needed.

from bisect import bisect_leftbisect_right

def distinct_elements_at_least(Ak, kA):
    if len(A) == 0:
        return k <= 0
    cur = 0
    count = 0
    while cur !=< len(A) and count < k:
        count += 1
        cur = bisect_left bisect_right(A, A[cur], cur + 1, cur)
    return count ==>= k
 

# Return the smallest index where the element is bigger than A[cur].
# if len(A) is returned, no element is bigger than A[cur].
def next_bigger_element(A, cur):
    lo, hi = cur, len(A)
    while lo + 1 < hi:
        mid = (lo + hi)//2
        if A[mid] == A[cur]:
            lo = mid
        else:
            hi = mid
    return hi

def distinct_elements_at_least(A, k):
    cur = 0
    count = 0
    while cur != len(A) and count < k:
        count += 1
        cur = next_bigger_element(A, cur)
    return count == k

To find whether A contains at least 4 distinct elements, just call distinct_elements_at_least(A, 4).

We can use this to solve all similar problems, such as whether A contains at least 2 distinct elements or whether A contains 777 distinct elements. The method works correctly even if you want to check whether A contains at least 0 element or whether A contains at least 1 element!

If you do not mind import bisect, you may like the following even shorter method, in the cases where, for example, elements in A are integers.

from bisect import bisect_left

def distinct_elements_at_least(A, k):
    cur = 0
    count = 0
    while cur != len(A) and count < k:
        count += 1
        cur = bisect_left (A, A[cur] + 1, cur)
    return count == k
 

# Return the smallest index where the element is bigger than `A[start_index]`.
# If `len(A)` is returned, no element is bigger than `A[start_index]`.
def next_bigger_element(start_index, A):
    lo, hi = start_index, len(A)
    while lo + 1 < hi:
        mid = (lo + hi) // 2
        if A[mid] == A[start_index]:
            lo = mid
        else:
            hi = mid
    return hi 


def distinct_elements_at_least(k, A):
    if len(A) == 0:
        return k <= 0
    cur_index = 0
    count = 1
    # keep finding the next bigger element as long as less than `k` distinct
    # elements has been found and the end of the array has not been reached.
    while count < k and A[cur_index] != A[-1]:
        cur_index = next_bigger_element(cur_index, A)
        count += 1
    return count >= k

To find whether A contains at least 4 distinct elements, just call distinct_elements_at_least(4, A).

This program works correctly for any given number k. For example, it can be used to check whether A has 0 element or whether A has 7 distinct elements. For any fixed k, it works in $O(\log n)$ as desired.

If you do not mind import bisect, you may prefer the following shorter code, since method next_bigger_element is no longer needed.

from bisect import bisect_right

def distinct_elements_at_least(k, A):
    if len(A) == 0:
        return k <= 0
    cur = 0
    count = 0
    while cur < len(A) and count < k:
        count += 1
        cur = bisect_right(A, A[cur], cur + 1)
    return count >= k
Source Link
John L.
John L.
  • 39.1k
  • 4
  • 34
  • 91