donnemartin / donnemartin/interactive-coding-challenges

kth-largest-element-in-array throws Exceptions for edge cases

Open
#269 0 comments 0 reactions 0 assignees View on GitHub
needs-review
Dominant language
Python
Stars
31.8k
Forks
4.7k
PR merge metrics
No merged PRs in 30d

Description

The given solution in Python throws a `TypeError` for the given example and `IndexError` for other examples. A couple of suggested changes:

1. Use integer division in line 13
2. Adjust k only once

### Something like this:
```
def kth_largest(l, k):
"""
Shorthand Quicksort
Runtime: O(n * log n)
"""
# kth largest element
# is k-1th element in output
def qsort(arr, pos):
middle = len(arr)//2
pivot = arr[middle]
smaller = [i for i in arr if i < pivot]
if pos < len(smaller):
return qsort(smaller, pos)
equal = [i for i in arr if i == pivot]
if pos < len(smaller) + len(equal):
return pivot
larger = [i for i in arr if i > pivot]
return qsort(larger, pos - len(smaller) - len(equal))

return qsort(l, k-1)
```

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.