Algorithms Project
Tasks 1 & 6
Faculty of Computer Science
Horus University
Team Members
إياد ضياء أحمد عبدالحليم — 932240029
أحمد حامد محمد عبدالعزيز أيوب — 931240062
يوسف محمد سيد عبدالواحد — 931240432
عبدالله مصطفى جابر عزالدين — 933240081
أحمد جمال عبدالمنطلب — 931240009
أيمن علي محمد شعيب — 931240050
Task 1: Max Product of Three
Problem Description
Given an integer array, the goal is to compute the maximum possible product of any three
distinct elements in the array.
Non-Recursive Pseudocode
function MaxProductNonRecursive(A):
if length(A) < 3: error
max1, max2, max3 = -INF, -INF, -INF
min1, min2 = +INF, +INF
for each x in A:
if x > max1:
max3, max2, max1 = max2, max1, x
else if x > max2:
max3, max2 = max2, x
else if x > max3:
max3 = x
if x < min1:
min2, min1 = min1, x
else if x < min2:
min2 = x
return max(max1*max2*max3, max1*min1*min2)
Steps Explanation
• Track the three largest values in the array.
• Track the two smallest values (important for negative products).
• Update maxima and minima while scanning.
• Compare product of three maxima vs. product of max1 * two smallest.
Python Code (Non-Recursive)
def max_product_of_three_non_recursive(nums):
if len(nums) < 3:
raise ValueError("Array must have at least 3 elements")
max1 = max2 = max3 = -10**18
min1 = min2 = 10**18
for x in nums:
if x > max1:
max3, max2, max1 = max2, max1, x
elif x > max2:
max3, max2 = max2, x
elif x > max3:
max3 = x
if x < min1:
min2, min1 = min1, x
elif x < min2:
min2 = x
return max(max1 * max2 * max3, max1 * min1 * min2)
Recursive Pseudocode
function MaxProductRecursive(A):
define rec(i, max1, max2, max3, min1, min2):
if i == length(A):
return (max1, max2, max3, min1, min2)
x = A[i]
update maxima
update minima
return rec(i+1, updated values)
return rec(0, -INF, -INF, -INF, +INF, +INF)
Python Code (Recursive)
def max_product_of_three_recursive(nums):
def rec(i, max1, max2, max3, min1, min2):
if i == len(nums):
return max1, max2, max3, min1, min2
x = nums[i]
if x > max1:
max3, max2, max1 = max2, max1, x
elif x > max2:
max3, max2 = max2, x
elif x > max3:
max3 = x
if x < min1:
min2, min1 = min1, x
elif x < min2:
min2 = x
return rec(i+1, max1, max2, max3, min1, min2)
return rec(0, -10**18, -10**18, -10**18, 10**18, 10**18)
Time Complexity
• Non-Recursive: O(n) time, O(1) space
• Recursive: O(n) time, O(n) recursion stack
Comparison
The non-recursive solution is more efficient in memory. The recursive variant provides the
required second algorithmic approach.
Test Cases
Input: [1, 2, 3] → Output: 6
Input: [-3, 1, 2, -2, 5, 6] → Output: 60
Task 6: Wiggle Sort
Problem Description
Reorder array elements so that: nums[0] < nums[1] > nums[2] < nums[3] ...
Non-Recursive Pseudocode
function WiggleSortNonRecursive(A):
for i from 0 to n-2:
if i is even and A[i] >= A[i+1]:
swap A[i], A[i+1]
if i is odd and A[i] <= A[i+1]:
swap A[i], A[i+1]
return A
Python Code (Non-Recursive)
def wiggle_sort_non_recursive(nums):
for i in range(len(nums)-1):
if i % 2 == 0 and nums[i] >= nums[i+1]:
nums[i], nums[i+1] = nums[i+1], nums[i]
elif i % 2 == 1 and nums[i] <= nums[i+1]:
nums[i], nums[i+1] = nums[i+1], nums[i]
return nums
Recursive Pseudocode
function WiggleSortRecursive(A):
define helper(i):
if i >= n-1: return
if i is even and A[i] >= A[i+1]: swap
if i is odd and A[i] <= A[i+1]: swap
helper(i+1)
helper(0)
return A
Python Code (Recursive)
def wiggle_sort_recursive(nums):
def helper(i):
if i >= len(nums)-1:
return
if i % 2 == 0 and nums[i] >= nums[i+1]:
nums[i], nums[i+1] = nums[i+1], nums[i]
elif i % 2 == 1 and nums[i] <= nums[i+1]:
nums[i], nums[i+1] = nums[i+1], nums[i]
helper(i+1)
helper(0)
return nums
Time Complexity
Both solutions run in O(n) time; recursive uses O(n) stack space.
Examples
Input: [1,5,1,1,6,4] → [1,6,1,5,1,4]
Input: [1,3,2,2,3,1] → [2,3,1,3,1,2]