Skip to main content

2 posts tagged with "Data Structures"

Fundamental data structures and their applications in programming and computer science.

View All Tags

Sliding Window Technique Made Easy: Master This Powerful Algorithm Pattern

· 3 min read
Sudip Parajuli
Sudip Parajuli
Full Stack Django Developer | Data Science | IoT and Robotics

The Sliding Window technique is one of the most powerful algorithmic patterns for solving array and string problems efficiently. It's a must-know technique for coding interviews and can transform O(n²) solutions into elegant O(n) algorithms.

Interactive Sliding Window Visualizer​

Try out different sliding window problems with our interactive visualizer below. Watch how the window slides across the input and see the algorithm in action!

Interactive Sliding Window Visualizer

Count Substring Occurrences
Find how many times a pattern appears in the string
Window [0, 2]
a
b
c
a
b
c
a
b
c
a
b
c
Normal
Current Window
Match Found
Comparing

How it works:

  • Create a window of size equal to pattern length
  • Slide the window from left to right across the string
  • At each position, compare window content with the pattern
  • Count matches and continue until end of string
  • Time Complexity: O(n) where n is string length

Python Implementation

🎯 Count Substring Occurrences
def count_substring(string, sub_string):
    """
    Count occurrences of substring using sliding window
    Time: O(n), Space: O(1)
    """
    win_size = len(sub_string)
    l_string = len(string)
    cnt = 0
    n_window_slides = l_string - win_size
    
    for i in range(n_window_slides + 1):
        curr_win = string[i:win_size + i]
        if sub_string == curr_win:
            cnt += 1
    
    return cnt

# Example usage
string = "abcabcabcabc"
pattern = "abc"
result = count_substring(string, pattern)
print(f"Pattern '{pattern}' found {result} times")  # Output: 4

🚀 Sliding Window Tips & Tricks

🎯 When to Use
  • Contiguous subarray/substring problems
  • Finding optimal values (min/max)
  • Pattern matching and counting
  • Character frequency problems
⚡ Performance Benefits
  • Reduces O(n²) to O(n) complexity
  • Eliminates redundant calculations
  • Uses constant extra space
  • Single-pass solution
🔧 Implementation Tips
  • Use hashmap for frequency tracking
  • Handle edge cases (empty input)
  • Choose fixed vs variable window
  • Optimize window updates

Sorting Algorithms

· One min read
Sudip Parajuli
Sudip Parajuli
Full Stack Django Developer | Data Science | IoT and Robotics

Bubble sort is a simple and straightforward sorting algorithm that compares two adjacent elements in the list and swaps them if they are in the wrong order. This process is repeated until the entire list is sorted.

Interactive Bubble Sort Visualizer

Try the interactive visualizer below to see how bubble sort works step by step!

Interactive Bubble Sort Visualizer

1000ms
64
34
25
12
22
11
90
Normal
Comparing
Swapping
Sorted

How to use:

  • Click Play to watch the bubble sort algorithm in action
  • Adjust the speed slider to control animation speed
  • Click Reset to return to the original array
  • Colors indicate: Normal (blue), Comparing (yellow), Swapping (red), Sorted (green)

Time Complexity Analysis

Best Case: O(n)
Already sorted array
Average Case: O(n²)
Random order
Worst Case: O(n²)
Reverse sorted
n=10
n=20
n=50
n=100
n=200
n=500
Best O(n)
Average O(n²)
Worst O(n²)

Python Implementation Examples

📝 Basic Implementation
def bubble_sort_basic(arr):
    """Basic bubble sort - O(n²) for all cases"""
    n = len(arr)
    
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    
    return arr

# Example usage
numbers = [64, 34, 25, 12, 22, 11, 90]
result = bubble_sort_basic(numbers.copy())
print(result)  # [11, 12, 22, 25, 34, 64, 90]
⚡ Optimized with Early Termination
def bubble_sort_optimized(arr):
    """Optimized bubble sort with early termination"""
    n = len(arr)
    
    for i in range(n):
        swapped = False
        
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        
        # Early termination if no swaps occurred
        if not swapped:
            break
    
    return arr
🔍 Explanation

The bubble_sort_basic function implements the basic bubble sort algorithm with a time complexity of O(n²) for all cases. The bubble_sort_optimized function adds an early termination condition to improve performance, especially for nearly sorted arrays.

Both functions take an array as input and return the sorted array. The optimized version checks if any swaps were made in each pass; if no swaps occur, it terminates early, indicating that the array is already sorted.