Python Code Examples: Solutions & Discussion
Hey guys! Today, we're diving deep into some classic Python coding problems and their solutions. Whether you're brushing up on your skills or tackling these for the first time, understanding these solutions is a fantastic way to boost your Python prowess. We'll break down each problem, walk through the code, and discuss the logic behind it. Let's get started!
1. Two Sum
Problem
Given an array of integers, find the indices of the two numbers that add up to a specific target. This is a classic problem that often appears in coding interviews, and it's a great way to demonstrate your understanding of basic data structures and algorithms.
Solution
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
num_to_index = {}
for i, num in enumerate(nums):
complement = target - num
if complement in num_to_index:
# Found the pair
return [num_to_index[complement], i]
# Store the current number with its index
num_to_index[num] = i
# This line is technically unreachable because the problem guarantees a solution
return []
Explanation
In this Two Sum solution, we use a dictionary called num_to_index to store each number from the input list along with its index. The core idea revolves around iterating through the nums list. For each num in nums, we calculate its complement by subtracting it from the target. The goal is to find a number in the list that, when added to num, equals the target.
If the complement is already present in our num_to_index dictionary, it means we've encountered the other number required to achieve the target sum. In this case, we return a list containing the index of the complement (retrieved from num_to_index) and the current index i. This list represents the pair of indices that satisfy the condition.
If the complement is not found in num_to_index, it implies that we haven't yet encountered its corresponding number in the list. In such cases, we store the current number num and its index i in the num_to_index dictionary. This ensures that if we encounter num's complement later in the list, we'll be able to quickly retrieve its index.
This approach optimizes the search process by leveraging the constant-time lookup property of dictionaries, making the overall time complexity of the solution O(n), where n is the number of elements in the input list nums. By efficiently storing and retrieving indices, this algorithm swiftly identifies the pair of numbers that sum up to the target.
2. Add Two Numbers
Problem
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
Solution
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def addTwoNumbers(self, l1, l2):
"""
:type l1: Optional[ListNode]
:type l2: Optional[ListNode]
:rtype: Optional[ListNode]
"""
dummy = ListNode(0)
current = dummy
carry = 0
# Loop while either list has nodes or there is a carry
while l1 or l2 or carry:
val1 = l1.val if l1 else 0
val2 = l2.val if l2 else 0
# Compute sum and carry
total = val1 + val2 + carry
carry = total // 10
new_digit = total % 10
# Append new node
current.next = ListNode(new_digit)
current = current.next
# Move to next nodes
if l1:
l1 = l1.next
if l2:
l2 = l2.next
return dummy.next
Explanation
The Add Two Numbers problem involves summing two numbers represented as linked lists, where each node contains a single digit, and digits are stored in reverse order. To solve this, we initialize a dummy node to simplify the handling of the head of the result list, along with a current pointer to traverse the result list and a carry variable to keep track of any carry-over from previous additions.
The algorithm iterates through the input linked lists l1 and l2 simultaneously, as long as there are nodes in either list or there is a carry remaining. Within each iteration, it retrieves the values val1 and val2 from the current nodes of l1 and l2, respectively, defaulting to 0 if a list has been exhausted. These values, along with any carry from the previous step, are summed up to obtain the total.
The carry for the next iteration is calculated by integer division of the total by 10, while the new_digit to be added to the result list is obtained by taking the modulus of the total by 10. A new node with this new_digit is appended to the result list, and the current pointer is advanced to this new node.
Finally, the algorithm advances the pointers of l1 and l2 to their respective next nodes, if available. This process continues until both lists are exhausted and there is no carry remaining. The next pointer of the dummy node, which points to the head of the result list, is then returned, providing the sum of the two numbers represented by the input linked lists.
3. Longest Substring Without Repeating Characters
Problem
Given a string, find the length of the longest substring without repeating characters. This is a common problem that tests your understanding of string manipulation and sliding window techniques.
Solution
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
char_index = {} # Stores the last index of each character
left = 0 # Left pointer of the window
max_length = 0 # Max length of substring without duplicates
for right, char in enumerate(s):
# If character is in the window, move left pointer
if char in char_index and char_index[char] >= left:
left = char_index[char] + 1
# Update the last seen index of the character
char_index[char] = right
# Update max length
max_length = max(max_length, right - left + 1)
return max_length
Explanation
The Longest Substring Without Repeating Characters problem requires finding the length of the longest substring within a given string s that contains no repeating characters. To solve this, we employ a sliding window approach along with a dictionary char_index to keep track of the last seen index of each character.
The algorithm initializes two pointers, left and right, representing the boundaries of the sliding window, and max_length to store the maximum length found so far. As the right pointer iterates through the string, the algorithm checks if the current character char is already present in the char_index dictionary and if its last seen index is within the current window (i.e., greater than or equal to left).
If a repeating character is encountered within the window, the left pointer is advanced to the position immediately after the previous occurrence of the character. This ensures that the substring within the window remains free of repeating characters. Regardless of whether a repeating character is encountered, the char_index dictionary is updated with the current index of the character, and the max_length is updated to the maximum of its current value and the length of the current window (right - left + 1).
By dynamically adjusting the window boundaries and tracking character occurrences, this algorithm efficiently identifies the longest substring without repeating characters, providing an optimal solution to the problem.
4. Median of Two Sorted Arrays
Problem
Given two sorted arrays, find the median of the combined sorted array. This is a more challenging problem that requires a good understanding of binary search.
Solution
class Solution(object):
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
m, n = len(nums1), len(nums2)
left, right = 0, m
while left <= right:
i = (left + right) // 2
j = (m + n + 1) // 2 - i
# Edge values
max_left_nums1 = float('-inf') if i == 0 else nums1[i-1]
min_right_nums1 = float('inf') if i == m else nums1[i]
max_left_nums2 = float('-inf') if j == 0 else nums2[j-1]
min_right_nums2 = float('inf') if j == n else nums2[j]
# Check if partition is correct
if max_left_nums1 <= min_right_nums2 and max_left_nums2 <= min_right_nums1:
# If total length is even
if (m + n) % 2 == 0:
return (max(max_left_nums1, max_left_nums2) + min(min_right_nums1, min_right_nums2)) / 2.0
else:
return float(max(max_left_nums1, max_left_nums2))
elif max_left_nums1 > min_right_nums2:
right = i - 1
else:
left = i + 1
Explanation
In the Median of Two Sorted Arrays problem, the objective is to find the median of the combined sorted array formed by merging two given sorted arrays, nums1 and nums2. To accomplish this efficiently, the algorithm employs a binary search approach.
The algorithm begins by ensuring that nums1 is the shorter array to simplify the binary search process. It then initializes variables m and n to store the lengths of nums1 and nums2, respectively, and sets up the binary search boundaries left and right to 0 and the length of nums1, respectively.
Within the binary search loop, the algorithm calculates the partition indices i and j for nums1 and nums2 such that the number of elements to the left of the partitions is equal to (m + n + 1) // 2. It then retrieves the maximum element to the left and the minimum element to the right of the partitions in both arrays, handling edge cases by using float('-inf') and float('inf') when necessary.
The algorithm checks if the partitions are correctly placed by verifying that the maximum element to the left of the partition in nums1 is less than or equal to the minimum element to the right of the partition in nums2, and vice versa. If this condition is satisfied, it means the median can be calculated based on the elements around the partitions.
If the total number of elements is even, the median is the average of the maximum of the left elements and the minimum of the right elements. If the total number of elements is odd, the median is simply the maximum of the left elements. If the partitions are not correctly placed, the binary search boundaries are adjusted based on whether the maximum element to the left of the partition in nums1 is greater than the minimum element to the right of the partition in nums2.
This binary search approach efficiently finds the median of the combined sorted array with a time complexity of O(log(min(m, n))), making it a highly performant solution.
5. Longest Palindromic Substring
Problem
Given a string, find the longest palindromic substring. This problem often involves dynamic programming or expanding from the center techniques.
Solution
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
if not s or len(s) == 1:
return s
start, end = 0, 0
# Helper function to expand from the center
def expandAroundCenter(left, right):
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
# Return the palindrome substring boundaries
return left + 1, right - 1
for i in range(len(s)):
# Odd length palindrome
l1, r1 = expandAroundCenter(i, i)
# Even length palindrome
l2, r2 = expandAroundCenter(i, i + 1)
# Choose the longer one
if r1 - l1 > end - start:
start, end = l1, r1
if r2 - l2 > end - start:
start, end = l2, r2
return s[start:end + 1]
Explanation
To solve the Longest Palindromic Substring problem, which involves finding the longest substring within a given string s that is a palindrome, this algorithm employs an approach that expands around the center.
The algorithm begins by handling edge cases where the input string s is empty or has a length of 1, in which case the string itself is returned as the longest palindrome. It initializes start and end variables to keep track of the boundaries of the longest palindrome found so far.
A helper function expandAroundCenter is defined to expand outwards from a given center (or centers) to identify palindromes. This function takes two indices, left and right, as input, representing the potential center(s) of a palindrome. It iteratively decrements left and increments right as long as the characters at these indices match and the indices remain within the bounds of the string. Once the expansion is no longer possible, the function returns the final boundaries of the palindrome.
The main part of the algorithm iterates through each character in the string s, considering it as a potential center of a palindrome. For each character, it calls the expandAroundCenter function twice: once to expand around a single character (for odd-length palindromes) and once to expand around two characters (for even-length palindromes).
After each expansion, the algorithm compares the length of the palindrome found with the length of the longest palindrome found so far. If the newly found palindrome is longer, the start and end variables are updated to reflect the boundaries of this palindrome. Finally, the algorithm returns the substring of s that corresponds to the longest palindrome found.
By expanding around the center, this algorithm efficiently explores all possible palindromic substrings within the given string, making it a reliable solution for finding the longest palindrome.
6. Zigzag Conversion
Problem
The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this:
P A H N
A P L S I I G
Y I R
And then read line by line: "PAHNAPLSIIGYIR"
Write the code that will take a string and make this conversion given a number of rows:
string convert(string s, int numRows);
Solution
class Solution(object):
def convert(self, s, numRows):
"""
:type s: str
:rtype: str
"""
if numRows == 1 or numRows >= len(s):
return s
# Create a list for each row
rows = [''] * numRows
cur_row = 0
going_down = False
# Traverse through the string
for char in s:
rows[cur_row] += char
# Change direction when reaching top or bottom
if cur_row == 0 or cur_row == numRows - 1:
going_down = not going_down
cur_row += 1 if going_down else -1
# Join all rows to form final string
return ''.join(rows);
Explanation
The Zigzag Conversion problem involves converting a given string s into a zigzag pattern based on a specified number of rows, numRows. To solve this problem, the algorithm simulates the process of writing the string in a zigzag manner and then reading it line by line.
The algorithm begins by handling edge cases where numRows is 1 or greater than or equal to the length of the string s. In these cases, the original string s is returned directly, as no zigzag conversion is needed.
For cases where zigzag conversion is required, the algorithm creates a list called rows to represent each row in the zigzag pattern. It initializes cur_row to 0 to keep track of the current row being written to, and going_down to False to indicate the direction of traversal (downwards or upwards).
The algorithm then iterates through each character in the input string s. For each character, it appends the character to the corresponding row in the rows list. After appending the character, it checks if the current row is either the top row (cur_row is 0) or the bottom row (cur_row is numRows - 1). If so, it reverses the direction of traversal by toggling the going_down flag.
Finally, the algorithm constructs the converted string by joining all rows in the rows list together. This converted string represents the zigzag pattern formed by writing the input string in a zigzag manner with the specified number of rows. This approach efficiently simulates the zigzag conversion process, providing an accurate and concise solution to the problem.
7. Reverse Integer
Problem
Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-231, 231 - 1], then return 0.
Solution
class Solution(object):
def reverse(self, x):
"""
:type x: int
:rtype: int
"""
INT_MAX = 2**31 - 1
INT_MIN = -2**31
result = 0
negative = x < 0
x = abs(x)
while x != 0:
pop = x % 10
x //= 10
# Check for overflow before multiplying by 10
if result > (INT_MAX - pop) // 10:
return 0
result = result * 10 + pop
return -result if negative else result
Explanation
To solve the Reverse Integer problem, which involves reversing the digits of a given 32-bit signed integer while considering potential overflow issues, the algorithm employs a systematic approach.
The algorithm begins by defining constants INT_MAX and INT_MIN representing the maximum and minimum values for a 32-bit signed integer, respectively. It initializes a result variable to 0, which will store the reversed integer, and determines whether the input integer x is negative by checking if it's less than 0. The absolute value of x is then taken to simplify the digit reversal process.
The algorithm enters a loop that continues as long as x is not equal to 0. Inside the loop, the algorithm extracts the last digit of x using the modulo operator (%) and stores it in the pop variable. The value of x is then updated by integer division (//) to remove the last digit.
Before appending the extracted digit to the result, the algorithm performs an overflow check. It verifies whether the current result is greater than the maximum possible value that can be achieved without causing overflow. If an overflow is detected, the algorithm immediately returns 0.
If no overflow is detected, the algorithm updates the result by multiplying it by 10 and adding the extracted digit pop. This effectively shifts the existing digits to the left and appends the new digit to the end. Finally, the algorithm checks whether the original input integer x was negative. If so, it negates the result to maintain the sign. The reversed integer is then returned as the output. This approach ensures accurate digit reversal while effectively handling potential overflow issues within the 32-bit signed integer range.
8. String to Integer (atoi)
Problem
Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer (similar to C/C++'s atoi function).
Solution
class Solution(object):
def myAtoi(self, s):
"""
:type s: str
:rtype: int
"""
INT_MAX = 2**31 - 1
INT_MIN = -2**31
i = 0
n = len(s)
# Skip leading whitespaces
while i < n and s[i] == ' ':
i += 1
if i == n:
return 0
# Check sign
sign = 1
if s[i] == '+':
i += 1
elif s[i] == '-':
sign = -1
i += 1
result = 0
# Convert digits to integer
while i < n and s[i].isdigit():
digit = int(s[i])
# Check overflow
if result > (INT_MAX - digit) // 10:
return INT_MAX if sign == 1 else INT_MIN
result = result * 10 + digit
i += 1
return sign * result
Explanation
The String to Integer (atoi) problem requires implementing a function that converts a string s into a 32-bit signed integer, mimicking the behavior of the atoi function in C/C++. To address this problem comprehensively, the algorithm follows a systematic approach.
The algorithm starts by defining INT_MAX and INT_MIN constants representing the maximum and minimum values for a 32-bit signed integer, respectively. It initializes an index i to 0 and the length of the string n for iteration purposes. Leading whitespaces are skipped by incrementing i until a non-whitespace character is encountered.
If the string is empty after skipping whitespaces, the algorithm returns 0. Otherwise, it checks for an optional sign character ('+' or '-') at the current index. If a sign character is present, the sign variable is set accordingly (1 for positive, -1 for negative), and the index i is incremented to move past the sign character.
Next, the algorithm iterates through the remaining characters of the string as long as they are digits. For each digit encountered, it converts the digit character to its integer equivalent and checks for potential overflow conditions. If multiplying the current result by 10 and adding the digit would exceed the maximum or minimum integer value, the algorithm returns INT_MAX or INT_MIN accordingly.
If no overflow occurs, the result is updated by multiplying it by 10 and adding the current digit. This process effectively accumulates the integer value represented by the digits in the string. Finally, the algorithm returns the result multiplied by the sign to account for the sign of the integer. This comprehensive approach ensures accurate string-to-integer conversion while handling various edge cases and potential overflow scenarios, making it a robust solution for the atoi problem.
9. Palindrome Number
Problem
Given an integer x, return true if x is a palindrome, and false otherwise.
Solution
class Solution(object):
def isPalindrome(self, x):
"""
:type x: int
:rtype: bool
"""
if x < 0:
return False
# Convert the number to string
x_str = str(x)
# Check if the string is equal to its reverse
return x_str == x_str[::-1]
Explanation
In addressing the Palindrome Number problem, which involves determining whether a given integer is a palindrome, the algorithm employs a straightforward approach that leverages string manipulation.
The algorithm begins by checking if the input integer x is negative. If x is negative, it cannot be a palindrome because palindromes read the same forwards and backward, and negative numbers have a sign that disrupts this symmetry. Therefore, if x is negative, the algorithm immediately returns False.
For non-negative integers, the algorithm converts the integer to a string using the str() function. This conversion is crucial because strings can be easily reversed and compared, which simplifies the palindrome check. Once the integer is converted to a string, the algorithm compares the string to its reverse using string slicing. Specifically, x_str[::-1] creates a reversed copy of the string x_str.
If the original string x_str is equal to its reversed counterpart, it means the integer is a palindrome, and the algorithm returns True. Otherwise, if the string is not equal to its reverse, the integer is not a palindrome, and the algorithm returns False. This approach effectively determines whether an integer is a palindrome by leveraging the simplicity and flexibility of string manipulation in Python.
10. Regular Expression Matching
Problem
Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*' where:
'.' Matches any single character. '*' Matches zero or more of the preceding element. The matching should cover the entire input string (not partial).
Solution
class Solution(object):
def isMatch(self, s, p):
"""
:type s: str
:type p: str
:rtype: bool
"""
m, n = len(s), len(p)
dp = [[False] * (n + 1) for _ in range(m + 1)]
# Empty string matches empty pattern
dp[0][0] = True
# Handle patterns like a*, a*b*, a*b*c* matching empty string
for j in range(2, n + 1):
if p[j - 1] == '*':
dp[0][j] = dp[0][j - 2]
for i in range(1, m + 1):
for j in range(1, n + 1):
if p[j - 1] == '.' or p[j - 1] == s[i - 1]:
dp[i][j] = dp[i - 1][j - 1]
elif p[j - 1] == '*':
# '*' can mean zero of previous character or more
dp[i][j] = dp[i][j - 2] or (dp[i - 1][j] and (p[j - 2] == s[i - 1] or p[j - 2] == '.'))
return dp[m][n]
Explanation
To tackle the Regular Expression Matching problem, which involves implementing regular expression matching with support for '.' and '*' wildcards, the algorithm utilizes dynamic programming. This approach allows for efficient handling of complex matching patterns.
The algorithm begins by initializing variables m and n to represent the lengths of the input string s and the pattern p, respectively. A 2D boolean array dp of size (m + 1) x (n + 1) is created to store the matching results, where dp[i][j] indicates whether the substring s[:i] matches the pattern p[:j]. The algorithm sets dp[0][0] to True because an empty string matches an empty pattern.
To handle patterns like "a*", "ab", and "abc*" matching an empty string, the algorithm iterates through the pattern p starting from the second character. If a '' is encountered at index j - 1, dp[0][j] is set to dp[0][j - 2], indicating that the pattern up to this point matches an empty string if the pattern without the '' matches an empty string.
Next, the algorithm iterates through the input string s and pattern p using nested loops. For each pair of characters s[i - 1] and p[j - 1], the algorithm checks the following conditions:
- If
p[j - 1]is either a '.' (which matches any single character) or matchess[i - 1], thendp[i][j]is set todp[i - 1][j - 1], indicating that the substrings[:i]matches the patternp[:j]if the substrings[:i-1]matches the patternp[:j-1]. - If
p[j - 1]is a '', the algorithm considers two possibilities: either the '' matches zero occurrences of the preceding character or matches one or more occurrences. If it matches zero occurrences,dp[i][j]is set todp[i][j - 2]. If it matches one or more occurrences,dp[i][j]is set todp[i - 1][j]if the preceding character in the pattern either matches the current character in the string or is a '.'.
Finally, the algorithm returns dp[m][n], which indicates whether the entire input string s matches the pattern p. This dynamic programming approach efficiently explores all possible matching scenarios, making it a robust solution for the regular expression matching problem.
Conclusion
So, there you have it! We've walked through solutions to ten classic Python problems. Remember, the key to mastering coding is practice, practice, practice! Dive into these problems, tweak the code, and try solving similar challenges. You've got this, guys! Happy coding!