In an earlier post, we saw how to compute the equillibrium index of an array. But it was a very ordinary implementation - O(n^2). We could do much better with some auxiliary space spent, i.e. we maintain an auxiliary array to keep a running sum of the elements to the left as we traverse the array.

Here is the idea. We would create an auxiliary array of the same size as the input array. As we traverse the input array from left to right, we compute the prefix sum of the elements in the array and store it in this auxiliary array (left_sum in the code fragment below). Now, left sum can be used to query, for example, the sum of elements to the left of any index i as we traverse the array.

We now traverse the input array, this time from right to left, and keep a running sum of the elements in a single variable (right_sum in code fragment below). As we traverse, we check for a match in the auxiliary array we had built earlier for the left sum, and if there is a match we have found an equillibrium point. Since we do array traversal only twice, this becomes an O(n) solution with O(n) auxiliary space for storing the prefix sums.

void eq_index(int arr[], int n)
{
  // compute the left sum
  int* left_sum = new int[n];
  left_sum[0] = arr[0];
  for (int i = 1; i < n; i++)
    left_sum[i] = left_sum[i-1] + arr[i-1];

  // traverse input array from the right,
  // computing right_sum and matching it with
  // left sum (i.e. looking for equillibrium)
  int right_sum = 0;
  for (int i = n-1; i >= 0; i--)
  {
    if (right_sum == left_sum[i])
      std::cout << "equillibrium found at index: " << i << std::endl;
    right_sum += arr[i];
  } 
}

Power of prefix sums!

The equillibrium point in a given array is said to be the index such that the sum of all the elements before the index equals the sum of all the elements to the right of the index.

For example, if the input array is [0, -3, 5, -4, -2, 3, 1, 0], the equillibrium indices are 7, 3 and 0. Note that 0 is an equillibrium index if the sum of all the elements until the end of the array are 0 and similarly, n-1 is an equillibrium index of all the elements from 0 until n-1 add up to 0.

Let us look at a very straight-forward solution. We could just traverse the array and for each element compute the sum of elements to the left and the sum of elements to the right (lsum and rsum in the code fragment below) and check if they are equal as we traverse the array.

void eq_index(int arr[], int n)
{
  int lsum, rsum;
  for (int i = 0; i < n; i++)
  {
    lsum = 0;
    rsum = 0;
    for (int j = 0; j < i; j++)
      lsum += arr[j];
    for (int j = i+1; j <n; j++)
      rsum += arr[j];
    if (lsum == rsum)
      std::cout << "equillibrium found at index: " << i << std::endl;
  }
}

As you can realize immediately, this is an O(n^2) solution. Can we do better?

Earlier, we saw how to reverse a sub-array given the window to be reversed. How do we reverse an array in subarray groups? For example, if our input array is [1, 2, 3, 4, 5, 6, 7, 8] and group size is 3, we want to reverse every group of 3 elements in the array and the remaining ones. Something like:

1 2 3 4 5 6 7 8                 -> input array
(3 2 1) 4 5 6 7 8               -> first group of 3 elements reversed;
                                   group denoted by (..)
(3 2 1) (6 5 4) 7 8             -> second group of 3 elements reversed
(3 2 1) (6 5 4) (8 7)           -> remaining elements (less than group size)
                                   reversed

The algorithm is very similar to the earlier one, just that we need to take care of the group boundaries while traversal and reversing, just like how we took care of boundaries while reversing subarrays.

void reverse_in_groups(int arr[], int n, int g)
{
  for (int i = 0; i < n; i += g)
  {
    int lo = i;
    int hi = min(i + g - 1, n - 1);
    while (lo < hi)
    {
      swap(&arr[lo++], &arr[hi--]);
    }
  }
}

Here, n denotes the size of the input array arr and g denotes the size of the group.

Let us see how do we compute the minimum absolute difference among elements of an array. Given that we are concerened about all the elements of the array tells us that we need to

1. Traverse all the elements of the array (so complexity is already O(n))
2. Maintain a running counter that captures the minimum difference as we traverse the array - the idea is also to initialize this variable to MAX value so that we can record the minimum difference easily

int min_abs_diff(int arr[], int n)
{
  int min_diff = INT8_MAX;
  for (int i = 0; i < n; i++)
  {
    int diff = abs(arr[i] - arr[(i+1) % n]);
    if (diff < min_diff)
      min_diff = diff;
  }
  return min_diff;
}

Note how we try not to overflow the array index (while evaluating arr[i+1]) by computing modulo n - the size of the array.

Let us write a very simple program to implement a simple variant of str.find() that we used in our previous post. Basically, we want to write a function that accepts an input string and a pattern string and identifies if the pattern forms a substring of the input string and if it does tells us the first index position of occurence in the input string.

The naïve way is to traverse the input string looking for the pattern string. In order to do this, whenever we encounter the first character of the pattern string in the input string, we need to remember it and check if the following characters in the input string are the subsequent characters in the pattern string as well. We need to do this check (if successful) for as many characters as the length of the pattern string - quite intuitive.

1. Traverse the input string
2. As we traverse the input string, check if we encounter the first character of the pattern string
   1. If the pattern string’s first character does not match the current index character of the input string, keep moving forward in the input string while still waiting for a match for the first character of the pattern string.
   2. If the pattern string’s first character does match the current index character of the input string, move forward in the pattern string and check if the second character of the pattern string matches the next character in the input string
   3. If we successfully match the subsequent characters of input string and we have reached the end of the pattern string (i.e. successfully matched as many characters as the length of the pattern string) return the index of the input string that matched the first character of the input string (from 2.2)

Let us write it down as a C++ function:

int pat_search(std::string s, std::string pat)
{
  int slen = s.length();
  int plen = pat.length();
  int res = -1;
  for (int i = 0; i <= slen - plen; i++)
  {
    int j;
    for (j = 0; j < plen; j++)
    {
      if (s[i+j] != pat[j])
        break;
    }
    if (j == plen)
      return i;
  }
  return res;
}

This algorithm however matches only the first occurence of the pattern and not all occurences (there might be more than one occurence of the pattern in the input string). How do we modify the above algorithm to handle this case?