Smaller Than - codepath/compsci_guides GitHub Wiki

TIP102 Unit 1 Session 1 Advanced (Click for link to problem statements)

Problem Highlights

• 💡 Difficulty: Easy
• ⏰ Time to complete: 10 mins
• 🛠️ Topics: Arrays, Nested Loops

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Q: What is the input to the function?

  • A: The input is a list of integers nums.

• Q: What is the expected output of the function?

  • A: The function should return a list where each element corresponds to the count of numbers in nums that are smaller than the respective element.

• Q: How is the count determined?

  • A: For each element nums[i], count how many elements nums[j] (where j != i) are smaller than nums[i].

• Q: Can there be duplicate elements in nums?

  • A: Yes, the list nums can contain duplicate elements.

• Q: What if the list is empty?

  • A: If the list is empty, the function should return an empty list.

-The function smaller_than_current() should take a list of integers, nums, and return a list where each element represents the count of numbers in nums that are smaller than the corresponding element, excluding itself.

HAPPY CASE
Input: [8, 1, 2, 2, 3]
Expected Output: [4, 0, 1, 1, 3]

Input: [6, 5, 4, 8]
Expected Output: [2, 1, 0, 3]

EDGE CASE
Input: [7, 7, 7, 7]
Expected Output: [0, 0, 0, 0]

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Iterate through the list using nested loops to compare each element with all other elements to count how many are smaller.

1. Initialize an empty list `result`.
2. For each index `i` in `nums`, do the following:
   - Initialize a counter `count` to 0.
   - For each index `j` in `nums`, check if `j` is not equal to `i` and if `nums[j]` is smaller than `nums[i]`.
   - If true, increment `count`.
   - Append `count` to `result`.
3. Return `result`

⚠️ Common Mistakes

• Forgetting to exclude the current element when counting.
• Off-by-one errors when accessing list indices.

I-mplement

Implement the code to solve the algorithm.

def smaller_than_current(nums):
    result = []
    for i in range(len(nums)):
        count = 0
        for j in range(len(nums)):
            if nums[j] < nums[i]:
                count += 1
        result.append(count)
    return result