1. Pointers
VC2M10A06: level 10: Implement algorithms that use data structures using pseudocode or a general purpose programming language
Using pointers in algorithms
1.1. Pointers
Pointers are objects that store a memory address, which can be that of another value located in computer memory.
Using pointers significantly improves performance for repetitive operations, like traversing iterable data structures.
For example, the two pointers technique is a technique that involves using two pointers that traverse through an array or a list from different starting points or directions.
The pointers move based on certain rules and constraints, and the algorithm stops once both pointers meet a certain condition.
1.2. Two pointers: palindrome checker
The code below checks if words are palindromes, that is, words that are spelled the same when reversed.
1def is_palindrome(string):
2 # Initialize pointers
3 left = 0
4 right = len(string) - 1
5 # Check all letters in the string
6 while left < right:
7 # If letters are not equal
8 # Decision -> Return False
9 if string[left] != string[right]:
10 return False
11 # Else, the letters are equal
12 # Decision -> Bring left and right closer and compare again
13 else:
14 left += 1
15 right -= 1
16 return True
17
18
19word_to_check = "racecar"
20print(f"{word_to_check} is a plaindrome:", is_palindrome(word_to_check))
21# racecar is a plaindrome True
22word_to_check = "racecars"
23print(f"{word_to_check} is a plaindrome:", is_palindrome(word_to_check))
24# racecars is a plaindrome False
25
In the example provided, the function is called with the word “racecar” as an argument and its result is printed. Since “racecar” is a palindrome, the function returns True.
The is_palindrome function takes a string as input and returns a boolean value indicating whether the string is a palindrome or not. A palindrome is a word, phrase, number, or other sequence of characters that reads the same forward and backward (ignoring spaces, punctuation, and capitalization).
The function uses two pointers, left and right, to traverse the string from both ends.
The first pointer, left, starts at the beginning of the string, while the second pointer, right, starts at the end of the string.
The function then enters a loop that continues until the two pointers meet.
Inside the loop, the function checks if the characters at the current pointers are equal.
If they are not equal, the function returns False because the string is not a palindrome.
If they are equal, it moves both pointers towards each other and checks again.
If all characters are checked and no unequal pair is found, the function returns True because the string is a palindrome.
1.3. Two pointers: sum in list
The code below checks if 2 numbers in the list add to a given sum.
1def isPairSum(A, N, X):
2 """
3 This function takes a sorted list of integers A,
4 the length of the list N, and an integer X as input.
5 It returns a tuple containing a boolean value and two integers from the list if there exists a pair of elements (A[i], A[j]) such that their sum is equal to X.
6 If no such pair exists, it returns False.
7 """
8 # represents first pointer
9 i = 0
10 # represents second pointer
11 j = N - 1
12 while i < j:
13 # If we find a pair
14 if A[i] + A[j] == X:
15 return True, A[i], A[j]
16 # If sum of elements at current pointers is less,
17 # move towards higher values by doing i+1
18 elif A[i] + A[j] < X:
19 i += 1
20 # If sum of elements at current pointers is more,
21 # move towards lower values by doing j-1
22 else:
23 j -= 1
24
25 return False
26
27
28# Main code
29if __name__ == "__main__":
30 # array to check
31 arr = [2, 3, 5, 8, 9, 10, 11]
32 # array should be sorted first
33 arr.sort()
34 # value to search for 3 values to sum to
35 val = 17
36 # size of the array
37 arrSize = len(arr)
38 # Function call
39 print(isPairSum(arr, arrSize, val))
The isPairSum function takes a sorted list of integers A, the length of the list N, and an integer X as input.
It returns a tuple containing a boolean value and two integers from the list if there exists a pair of elements (A[i], A[j]) such that their sum is equal to X.
If no such pair exists, it returns False.
The function uses two pointers, i and j, to traverse the list from both ends.
The first pointer, i, starts at the beginning of the list, while the second pointer, j, starts at the end of the list.
The function then enters a loop that continues until the two pointers meet.
Inside the loop, the function checks if the sum of the elements at the current pointers is equal to X.
If it is, the function returns True and the values of the two elements.
If the sum is less than X, it moves the first pointer towards higher values by incrementing it.
If the sum is greater than X, it moves the second pointer towards lower values by decrementing it.
If no pair is found by the time the loop exits, the function returns False.
1.4. Two pointers: Length of longest substring
The code below returns the length of the longest string within the string.
1def length_of_longest_substring(s):
2 """
3 This function takes a string s as input and returns the length of the longest substring without repeating characters.
4 """
5 chars = set()
6 left = right = max_len = 0
7 while right < len(s):
8 if s[right] not in chars:
9 chars.add(s[right])
10 right += 1
11 max_len = max(max_len, right - left)
12 else:
13 chars.remove(s[left])
14 left += 1
15 return max_len
16
17
18s = "a-bc-d-e"
19result = length_of_longest_substring(s)
20print(f"The length of the longest substring without repeating characters in '{s}' is {result}.")
21# The length of the longest substring without repeating characters in 'a-bc-d-e' is 4.
22
23s = "ab-cd-e-fg-h-ij-k"
24result = length_of_longest_substring(s)
25print(f"The length of the longest substring without repeating characters in '{s}' is {result}.")
26# The length of the longest substring without repeating characters in 'ab-cd-e-fg-h-ij-k' is 5.
The length_of_longest_substring function takes a string s as input and returns the length of the longest substring without repeating characters.
The function uses two pointers, left and right, to keep track of the current substring.
It also initializes a set chars to keep track of the characters in the current substring and a variable max_len to keep track of the maximum length found so far.
The function then enters a loop that continues until the right pointer reaches the end of the string.
Inside the loop, the function checks if the character at the right pointer is not in the set chars.
If it is not, it adds the character to the set, increments the right pointer, and updates max_len with the maximum value between its current value and the length of the current substring.
If the character at the right pointer is already in the set chars, it means that there is a repeating character in the current substring.
In this case, the function removes the character at the left pointer from the set and increments the left pointer to move to the next character.
If all characters are checked and no longer substring is found, the function returns max_len.
In this example, the function is called with the string “a-bc-d-e” as an argument and its result is assigned to the variable result. The function returns 4 because “a-bc-d-e” is the longest substring without repeating characters. The result is then printed.
The code below modifies the code above to return the length of the longest string within the string as well as the substring.
1def length_of_longest_substring(s):
2 """
3 This function takes a string s as input and returns the length of the longest substring without repeating characters and the substring itself.
4 """
5 chars = set()
6 left = right = max_len = 0
7 max_substring = ""
8 while right < len(s):
9 if s[right] not in chars:
10 chars.add(s[right])
11 right += 1
12 if max_len < right - left:
13 max_len = right - left
14 max_substring = s[left:right]
15 else:
16 chars.remove(s[left])
17 left += 1
18 return max_len, max_substring
19
20
21s = "a-bc-d-e"
22result, substring = length_of_longest_substring(s)
23print(f"The longest substring without repeating characters in '{s}' is '{substring}', with length: {result}.")
24# The longest substring without repeating characters in 'a-bc-d-e' is 'a-bc', with length: 4.
25
26s = "ab-cd-e-fg-h-ij-k"
27result, substring = length_of_longest_substring(s)
28print(f"The longest substring without repeating characters in '{s}' is '{substring}', with length: {result}.")
29# The longest substring without repeating characters in 'ab-cd-e-fg-h-ij-k' is 'ab-cd', with length:
305.
1.5. Two pointers: longest mountain
The code below returns the length of the longest mountain and its length from a list of numbers.
1def longest_mountain(A):
2 """
3 Finds the longest ascending-descending sequence in the given set of numbers.
4
5 Parameters:
6 A (list): The list of numbers.
7
8 Returns:
9 int: The length of the longest ascending-descending sequence in the given list.
10 list: The longest ascending-descending sequence in the given list.
11 """
12
13 N = len(A)
14 mountan_length = base = 0
15 longest_seq = []
16 while base < N:
17 end = base
18 if end + 1 < N and A[end] < A[end + 1]:
19 while end + 1 < N and A[end] < A[end + 1]:
20 end += 1
21 if end + 1 < N and A[end] > A[end + 1]:
22 while end + 1 < N and A[end] > A[end+1]:
23 end += 1
24 if mountan_length < end - base + 1:
25 mountan_length = end - base + 1
26 longest_seq = A[base:end+1]
27 base = max(end, base + 1)
28 return mountan_length, longest_seq
29
30A = [2, 1, 4, 7, 3, 2, 5]
31length, sequence = longest_mountain(A)
32print(f"The longest mountain sequence is: {sequence}, with length: {length}")
33# The longest mountain sequence is: [1, 4, 7, 3, 2], with length: 5
The longest_mountain function takes in a list of numbers A as an input and returns the length and the longest ascending-descending sequence (mountain) in the given list.
The function starts by initializing the variables mountain_length, base, and longest_seq to 0, 0, and an empty list, respectively.
The variable mountain_length will keep track of the length of the longest mountain found so far, while longest_seq will keep track of the longest mountain sequence itself.
The function then enters a while loop that continues until the variable base is less than the length of the input list A.
Inside the loop, the variable end is set to the value of base.
The function then checks if end + 1 is less than the length of A and if the value at index end in list A is less than the value at index end + 1.
If this condition is true, it means that we have found an ascending sequence.
The function then enters another while loop that continues until end + 1 is less than the length of A and the value at index end in list A is less than the value at index end + 1.
Inside this loop, we increment the value of end by 1 to move forward in the ascending sequence.
After exiting this inner while loop, we check if end + 1 is less than the length of A and if the value at index end in list A is greater than the value at index end + 1.
If this condition is true, it means that we have found a descending sequence after an ascending sequence, which forms a mountain.
The function then enters another while loop that continues until end + 1 is less than the length of A and the value at index end in list A is greater than the value at index end + 1.
Inside this loop, we increment the value of end by 1 to move forward in the descending sequence.
After exiting this inner while loop, we check if the current mountain length (end - base + 1) is greater than our current maximum mountain length (mountain_length).
If it is, we update our maximum mountain length to be equal to our current mountain length (mountain_length = end - base + 1) and update our longest mountain sequence (longest_seq = A[base:end+1]) to be equal to our current mountain sequence.
Finally, we update our base index to be equal to either our current end index or our current base index plus one (base = max(end, base + 1)), whichever is greater.
This ensures that we move forward in our input list and do not get stuck in an infinite loop.
After exiting the outer while loop, we return our maximum mountain length and longest mountain sequence as a tuple.
In the example code, the function is called with an input list [2, 1, 4, 7, 3, 2, 5].
The function returns (5, [1, 4, 7, 3, 2]), which means that the longest mountain sequence in the input list is [1, 4, 7, 3, 2], with a length of 5.