Algorithms - lesson 2 | HackIndia Skills

Key point

Core idea

Sorting changes the shape of a problem. Searching uses that shape to avoid checking every item.

Before coding, ask: can sorted order remove choices, reveal duplicates, or make yes/no decisions monotonic?

When sorting helps

In placement rounds, sorting is often the first move when order does not matter in the final answer. It helps with duplicates, intervals, pairing, closest values, and ranking.

Sorting costs time, usually O(n log n). That is fine if it makes the rest of the solution simple and correct.

Your to-do

Sort-first checklist

Do each one yourself, then tap it to tick it off. The ticks are only a checklist for you: they are not marked or scored.

Check if the original order is important. If yes, do not sort blindly.
Sort numbers, strings, or pairs using the natural key you need.
Scan once after sorting to find duplicates, gaps, pairs, or merged ranges.
Write the complexity as O(n log n) for sorting plus O(n) for the scan.
Add a small sample run so your repo proves the code works.

0 of 5 done

Common mistake

Do not sort just because it feels neat. If the problem asks for original indices, sorting can lose information.

Fix this by sorting pairs like (value, index), or by using a map when original positions matter.

When search helps

Use linear search for small unsorted data or when no order exists. Use binary search when the array is sorted, or when you can test a yes/no condition over an ordered answer space.

The yes/no condition must flip only once. Example: if speed k can finish work on time, then any bigger speed also works. That is binary-searchable.

Example

Example: lower bound

Lower bound finds the first index where arr[index] is greater than or equal to target. It is useful for insert position, counts, and range queries.

Notice the loop keeps the answer inside left. No special case is needed after the loop.

def lower_bound(arr, target):
    left, right = 0, len(arr)

    while left < right:
        mid = (left + right) // 2

        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid

    return left

nums = [2, 4, 4, 7, 9]
print(lower_bound(nums, 4))   # 1
print(lower_bound(nums, 5))   # 3
print(lower_bound(nums, 10))  # 5

Tip

Use AI carefully

You can ask ChatGPT or Gemini for edge cases after you write your approach. Paste your problem statement, your idea, and your code.

Check what it returns. Test empty input, one item, duplicates, negative numbers, already sorted input, and target not found.