You are given an array S of n integers and another integer k. Describe an algorithm that determines whether or not there exist two elements in S whose absolute difference is exactly k. Find the optimal algorithm for:

1. Worst case runtime
2. Expected runtime