Find Invalid IP Addresses solution and explanation
4 more videos on this problem
LeetCode HARD 3451: Find Invalid IP Addresses | SQL REGEX Trick Every Data Scientist Should KnowEveryday Data Science · 13:49 · 587 views
LeetCode 3451: Find Invalid IP Addresses || LeetCode - Hard || #3451 #leetcode #insightvanta #sqlInsightVanta · 26:35 · 372 views
Find Invalid IP AddressesOwen Wu · 6:17 · 348 views
Find Invalid IP Addresses – LeetCode 3451 Explained (PostgreSQL Tutorial)Sumanshu Nankana · 23:57 · 51 views
Oversimplifying Leetcode problem 3451Fuad · 11:13 · 39 views
The problem
Table: logs
+-------------+---------+ | Column Name | Type | +-------------+---------+ | log_id | int | | ip | varchar | | status_code | int | +-------------+---------+ log_id is the unique key for this table. Each row contains server access log information including IP address and HTTP status code.
Write a solution to find invalid IP addresses. Each octet in an IP address contains between 1 and 3 digits. An IPv4 address is invalid if it meets any of these conditions:
- Contains a number greater than
255in any octet. - Has leading zeros in any octet (for example,
01.02.03.04). - Has fewer or more than
4octets.
Return the result table ordered by invalid_count, ip in descending order respectively.
The result format is in the following example.
Example:
Input:
logs table:
+--------+---------------+-------------+ | log_id | ip | status_code | +--------+---------------+-------------+ | 1 | 192.168.1.1 | 200 | | 2 | 256.1.2.3 | 404 | | 3 | 192.168.001.1 | 200 | | 4 | 192.168.1.1 | 200 | | 5 | 192.168.1 | 500 | | 6 | 256.1.2.3 | 404 | | 7 | 192.168.001.1 | 200 | +--------+---------------+-------------+
Output:
+---------------+--------------+ | ip | invalid_count| +---------------+--------------+ | 256.1.2.3 | 2 | | 192.168.001.1 | 2 | | 192.168.1 | 1 | +---------------+--------------+
Explanation:
- 256.1.2.3 is invalid because 256 > 255
- 192.168.001.1 is invalid because of leading zeros
- 192.168.1 is invalid because it has only 3 octets
The output table is ordered by invalid_count, ip in descending order respectively.
Approach overview
Problem Overview: You get a logs table with a log_id and an ip string. An IP is invalid if it is not a valid IPv4 address. Return each invalid IP with how many log rows contain it, sorted by count descending, then IP descending.
Approach 1: Simulation with octet parsing (O(n x L) time, O(n) space)
Split each IP string on the dot character and check the result. A valid IPv4 address must have exactly four parts. Each part must be non-empty, contain only digits, have no leading zero unless it is exactly 0, and fall between 0 and 255. In MySQL, you run these checks with SUBSTRING_INDEX and LENGTH to count separators and extract each octet. In Pandas, you use str.split('.') and apply a per-row validator. Any row that fails a check is invalid. Then you group by IP and count. Use this when you want explicit, readable rules that match the problem statement exactly.
Approach 2: Regex pattern match (O(n x L) time, O(n) space)
Collapse the validation into one pattern. In MySQL, REGEXP can match four octets where each octet is 25[0-5], 2[0-4][0-9], 1[0-9][0-9], [1-9]?[0-9], joined by literal dots, anchored with ^ and $. Rows that do not match are invalid. The filter is a single predicate, so the query is shorter. The cost is the same because the regex engine still scans each string once per row. Use this when you need compact SQL and you are comfortable reading anchored alternations.
Recommended for interviews: Interviewers expect the simulation approach because it proves you know the edge cases: wrong segment count, leading zeros, values above 255, and empty segments. The regex version shows fluency with pattern matching in SQL. Write the octet-level checks first, then mention the regex as a compact alternative. Grouping and sorting in the final query stays O(n) hash aggregation plus a sort over distinct invalid IPs.
Related topics: database, string, simulation.
Solution
Thinking
We count invalid IPv4 addresses in the logs. A valid address has four octets, each a
0..255integer with no leading zeros.A SQL regex can express this, but leading zeros plus ranges are awkward; splitting in Pandas is clearer.
Split on
., check that each piece is a digit string in range and equalsstr(int). Count invalid IPs and sort by count then address, both descending.
We can determine if an IP address is invalid based on the following conditions:
- The number of
.in the IP address is not equal to3; - Any octet in the IP address starts with
0; - Any octet in the IP address is greater than
255.
Then we group the invalid IP addresses and count the occurrences of each invalid IP address invalid_count, and finally sort by invalid_count and ip in descending order.
SELECT
ip,
COUNT(*) AS invalid_count
FROM logs
WHERE
LENGTH(ip) - LENGTH(REPLACE(ip, '.', '')) != 3
OR SUBSTRING_INDEX(ip, '.', 1) REGEXP '^0[0-9]'
OR SUBSTRING_INDEX(SUBSTRING_INDEX(ip, '.', 2), '.', -1) REGEXP '^0[0-9]'
OR SUBSTRING_INDEX(SUBSTRING_INDEX(ip, '.', 3), '.', -1) REGEXP '^0[0-9]'
OR SUBSTRING_INDEX(ip, '.', -1) REGEXP '^0[0-9]'
OR SUBSTRING_INDEX(ip, '.', 1) > 255
OR SUBSTRING_INDEX(SUBSTRING_INDEX(ip, '.', 2), '.', -1) > 255
OR SUBSTRING_INDEX(SUBSTRING_INDEX(ip, '.', 3), '.', -1) > 255
OR SUBSTRING_INDEX(ip, '.', -1) > 255
GROUP BY 1
ORDER BY 2 DESC, 1 DESC;import pandas as pd
def find_invalid_ips(logs: pd.DataFrame) -> pd.DataFrame:
def is_valid_ip(ip: str) -> bool:
octets = ip.split(".")
if len(octets) != 4:
return False
for octet in octets:
if not octet.isdigit():
return False
value = int(octet)
if not 0 <= value <= 255 or octet != str(value):
return False
return True
logs["is_valid"] = logs["ip"].apply(is_valid_ip)
invalid_ips = logs[~logs["is_valid"]]
invalid_count = invalid_ips["ip"].value_counts().reset_index()
invalid_count.columns = ["ip", "invalid_count"]
result = invalid_count.sort_values(
by=["invalid_count", "ip"], ascending=[False, False]
)
return resultComplexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simulation (octet parsing) | O(n x L) | O(n) | Interviews, explicit validation rules, debugging edge cases |
| Regex pattern match | O(n x L) | O(n) | Compact SQL, single predicate filter |
Frequently asked questions
Find Invalid IP Addresses Python solution?
In Pandas, split each ip with str.split('.', expand=True), check that there are four columns, convert each octet to integer, and flag values outside 0 to 255 or with leading zeros. Filter the invalid rows, groupby ip to count them, then sort by count descending and ip descending.
Is Find Invalid IP Addresses easy or hard?
Find Invalid IP Addresses is rated Hard on FleetCode. The difficulty comes from handling all IPv4 edge cases correctly, such as leading zeros, empty octets, and out-of-range values, and from combining validation with aggregation and a two-key sort in one query.
How to solve Find Invalid IP Addresses in O(n)?
Treat each IP string as a fixed-size input. Validate it in one pass by splitting on dots and checking each octet, which is O(L) per row and constant for valid IPv4 lengths. Then filter invalid rows, group by IP, and sort the distinct results. The total work is linear in the number of rows.
What is the best approach for Find Invalid IP Addresses?
The best approach is to validate each IP string against IPv4 rules, then group the invalid rows by IP and count them. Split on dots, check four octets, reject leading zeros and values above 255, and aggregate with GROUP BY in MySQL or groupby in Pandas.
What data structure is used in Find Invalid IP Addresses?
The solution uses a table scan with string functions for validation and a hash-based GROUP BY for counting invalid IPs per address. In Pandas, the same logic uses a Series of strings and a groupby over a hash-indexed result. No advanced data structure like a trie or heap is required.
What is the time complexity of Find Invalid IP Addresses?
The time complexity is O(n x L), where n is the number of log rows and L is the maximum length of an IP string. Each row is scanned once for validation, and grouping adds O(n) hash aggregation. Since IPv4 strings have bounded length, this is effectively linear in n.
Is Find Invalid IP Addresses asked at Google, Amazon, or Meta?
Find Invalid IP Addresses is tagged as a Database problem on LeetCode, and it is a hard-rated SQL question. Database questions like this one appear in interview loops at large tech companies, but exact company frequency varies by team and year, so check recent reports for your target role.