Find the Index of the First Occurrence in a String

Find the Index of the First Occurrence in a String - Problem

Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

This is a classic string matching problem where we need to find if one string exists as a substring within another string and return its starting position.

Input & Output

Example 1 — Basic Case

$ Input: haystack = "sadbutsad", needle = "sad"

› Output: 0

💡 Note: "sad" occurs at index 0 and 6. The first occurrence is at index 0, so we return 0.

Example 2 — Not Found

$ Input: haystack = "leetcode", needle = "leeto"

› Output: -1

💡 Note: "leeto" did not occur in "leetcode", so we return -1.

Example 3 — Single Character

$ Input: haystack = "hello", needle = "ll"

› Output: 2

💡 Note: "ll" occurs at index 2 in "hello", so we return 2.

Constraints

1 ≤ haystack.length, needle.length ≤ 10⁴
haystack and needle consist of only lowercase English characters.

Visualization

Tap to expand

Understanding the Visualization

Input

Two strings: haystack to search in, needle to find

Search Process

Check each position in haystack for needle match

Output

Return index of first occurrence or -1 if not found

Key Takeaway

🎯 Key Insight: Check each position systematically until we find a complete match

Asked in

f Facebook 25 a Amazon 20 M Microsoft 18 G Google 15

The key insight is to systematically check each position in the haystack string to see if the needle matches starting from that position. The brute force approach works well for this problem with O(n×m) time complexity. For production code, using built-in string search methods like indexOf() or find() is recommended. Time: O(n×m), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Built-in String Search	O(n×m)	O(1)	Use language built-in string search methods
Two Pointers with Smart Skip	O(n×m)	O(1)	Use two pointers with optimized character comparison
Brute Force - Check Every Position	O(n×m)	O(1)	Check needle at every possible position in haystack

Built-in String Search — Algorithm Steps

Step 1: Handle edge cases (empty needle)
Step 2: Use built-in string search method
Step 3: Return the result directly

Visualization

Tap to expand

Step-by-Step Walkthrough

Input Strings

haystack and needle are provided

Built-in Search

Language's optimized search function processes both strings

Return Index

Function returns the first occurrence index or -1

Code -

solution.c — C

#include <stdio.h>
#include <string.h>

int solution(char* haystack, char* needle) {
    if (strlen(needle) == 0) return 0;
    
    char* result = strstr(haystack, needle);
    return result ? result - haystack : -1;
}

int main() {
    char haystack[10001], needle[10001];
    fgets(haystack, sizeof(haystack), stdin);
    fgets(needle, sizeof(needle), stdin);
    haystack[strcspn(haystack, "\n")] = 0;
    needle[strcspn(needle, "\n")] = 0;
    int result = solution(haystack, needle);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n×m)

Built-in methods typically use optimized brute force or better algorithms

✓ Linear Growth

Space Complexity

O(1)

No extra space needed beyond input strings

✓ Linear Space

95.0K Views

Medium Frequency

~15 min Avg. Time

3.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Built-in String Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler