Skip to content

Bug Report for k-closest-points-to-origin #6207

Description

@Swagget

Bug Report for https://neetcode.io/problems/k-closest-points-to-origin

Please describe the bug below and include any steps to reproduce the bug or screenshots if possible.

This is my code, with a significant bug. Quick sort is implemented but instead of comparing the elements with the pivot element, i'm only comparing the "left" or dividor with the pivot. Which is totally 100% wrong. But I'm passing 22/23 test cases.

I should be failing a significant number of test cases, can you make sure that the test cases are actually rigorous?

class Solution:
def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
# First create a list of distances from origin, with the same indices.
self.distances = [point[0]**2 + point[1]**2 for point in points]
self.indices = [ele for ele in range(len(points))]
self.confirmed_close_points = []
self.remaining_points = k
self.k = k
# Call quicksort then. Since order doesn't matter, that would be a great approach.
self.quicksort(0,len(points)-1)

    to_return = [points[ele] for ele in self.confirmed_close_points]
    return to_return

def quicksort(self, start, end): # Keep calling quicksort on the left side arrays. Discard the right side arrays unless left is small. End is a valid pivot.
    if start > end:
        return
    pivot_val = self.distances[end]
    divider = start
    for i in range(start, end):
        if self.distances[divider] < pivot_val: # INSANE BUG HERREEE!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
            self.swap(divider, i)
            divider += 1
    self.swap(end, divider) # Now divider is the exact index of the pivot

    if divider - start == self.remaining_points: # This is the points to the left of the pivot, as long as you don't include divider.
        self.confirm(start, divider-1)
        return True
    if divider - start == self.remaining_points - 1:
        self.confirm(start, divider)
        return True
    elif 1 + divider - start < self.remaining_points: # This points are confirmed, and we call quick sort on the larger than pivot points.
        self.confirm(start, divider)
        self.quicksort(divider + 1, end)
    elif divider - start > self.remaining_points: # We discard the larger points and continue to search among the smaller points
        self.quicksort(start, divider-1)

def swap(self, a, b):
    self.distances[a], self.distances[b] = self.distances[b], self.distances[a]
    self.indices[a], self.indices[b] = self.indices[b], self.indices[a]

def confirm(self, start, end): # This will add the points to the confirmed points and remove them from the remaining points, including start, and including end.
    for ele in range(start, end+1):
        self.confirmed_close_points.append(self.indices[ele])
        self.remaining_points -= 1

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions