Table of contents


Introduction to brute force algorithm

Brute force algorithm is an algorithm that goes straight forward, through all cases to get suitable solutions.

For example, we have a dictionary, and we want to find a word in it. With brute force algorithm, we will go with the natural order - from A to Z of this dictionary. If this word starts with z character, it takes so much time to find it.

So, in this article, we will learn how to use brute force algorithm for some specific problems.


Search an element in an array

To search element in an array, we will apply brute force algorithm by scanning all array’s elements.

/**
 * Using linear search to scan all elements
 *
 * @param: nums - an array to be scanned
 * @param: target
 * @return: an index of target element, or if not found, return -1
 */
public int find(int[] nums, int target) {
    int len = nums.length;
    for (int i = 0; i < len; ++i) {
        if (nums[i] == target) {
            return i;
        }
    }

    return -1;
}

The complexity of this solution:

  • Time complexity: O(n)
  • Space complexity: O(1)

To optimize the time complexity of the above solution, we will use the lef-right algorithm.

/**
 * Using two pointer to scan an array
 *
 * @param: nums - an array to be scanned
 * @param: target
 * @return: an index of target element, or if not found, return -1
 */
public int find(int[] nums, int target) {
    int len = nums.length;
    int left = 0;
    int right = len - 1;

    while (left <= right) {
        if (nums[left] == target) return nums[left];
        if (nums[right] == target) return nums[right];

        ++left;
        --right;
    }

    return -1;
}

The complexity of this optimal solution:

  • Time complexity: O(n/2)
  • Space complexity: O(1)


Sorting an array

To apply brute force in sorting element in an array, we can do like the above:

public void sort(int[] nums) {
    int len = nums.length;

    for (int i = 0; i < len; ++i) {
        for (int j = 0; j < len - i - 1; ++j) {
            if (nums[j] > nums[j + 1]) {
                int tmp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = tmp;
            }
        }
    }
}

The complexity of this bubble sort is:

  • Time complexity: O(n^2)
  • Space complexity: O(1)

The problem of an above solution is that it sorts an array even if an array is sorted, the swapping operation is redundancy.

So, to optimize an above solution, we can use boolean isSwapped to check whether an array is sorted or not.

public void sort(int[] nums) {
    int len = nums.length;
    boolean isSwapped;

    for (int i = 0; i < len; ++i) {
        isSwapped = false;
        for (int j = 0; j < len - i - 1; ++j) {
            if (nums[j] > nums[j + 1]) {
                int tmp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = tmp;

                isSwapped = true;
            }
        }

        if (!isSwapped) {
            break;
        }
    }
}


Find the contiguous subarray has largest sum

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

For example:

Input: [-2, 1, -3, 4, -1, 2, 1, -5, 4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

To apply the brute force algorithm, we need to scan subarray with the dynamic length. It means that:

  • the outter loop will be used to set the start index of a subarray.
  • the inner loop will be used to set the last index of a subarray.
  • the most inner loop will loop from start index to last index.

Below is a source code for this problem:

public int maxSubArray(int[] nums) {
    int len = nums.length;
    int max = Integer.MIN_VALUE;

    for (int start = 0; start < len; ++start) {
        for (int end = start + 1; end <= len; ++end) {
            int sum = 0;
            for (int i = start; i < end; ++i) {
                sum += nums[i];
            }

            max = Math.max(max, sum);
        }
    }

    return max;
}

The complexity of this solution:

  • Time complexity: O(n^3).
  • Space complexity: O(1).

The above 3rd inner loop is redudant because we will calculate the sum of the elements in a subarray again. Then we can reduce it to 2 loops.

public int maxSubArray(int[] nums) {
    int max = Integer.MIN_VALUE;
    for (int start = 0; start < nums.length; start++) {
        int sum = 0;

        for (int end = start; end < nums.length; end++) {
            sum += nums[end]; 
            max = Math.max(max, sum);
        }
    }

    return max;
}

The complexity of this solution:

  • Time complexity: O(n^2).
  • Space complexity: O(1).

So to iterate all subarrays, we will use this 2 loops version.

Beside using Brute Force solution, there are some other solutions:

  • Kadane’s Algorithm: Time complexity is O(n), Space complexity is O(1).
  • Divide and Conquer: Time complexity is O(nlogn).
  • Dynamic Programming.


Longest palindrome substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

For example:

Example 1:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:
Input: "cbbd"
Output: "bb"

With this problem, we can use brute force with some ways:

  1. Brute Force: Scan all substring that we can. We can use the similar idea in the section Find the contiguous subarray has largest sum.

    • Based on the start index and end index of substring.

        public String longestPalindrome(String s) {
      int n = s.length();
      String res = "";

      for (int start = 0; start < n; ++start) {
          for (int end = start; end < n; ++end) {
              String sub = s.substring(start, end + 1);
              if (sub.length() > res.length() && isPalindrome(sub)) {
                  res = sub;
              }
          }
      }
      return res;
  }

  private boolean isPalindrome(String s) {
      int left = 0;
      int right = s.length() - 1;

      while (left < right) {
          if (s.charAt(left++) != s.charAt(right--)) {
              return false;
          }
      }
      return true;
  }

    • Based on the length of each substring.

        public String longestPalindrome(String s) {
      int n = s.length();
      String longestPal = "";

      for (int len = 1; len <= n; ++len) {
          for (int start = 0; start <= n - len; ++start) {
              String sub = s.substring(start, start + len);
                    
              if (isPalindrome(sub) && sub.length() > longestPal.length()) {
                  longestPal = sub;
              }
          }
      }

      return longestPal;
  }

  private boolean isPalindrome(String str) {
      int left = 0;
      int right = str.length() - 1;

      while (left < right) {
          if (str.charAt(left++) != str.charAt(right--)) {
              return false;
          }
      }
      return true;
  }

    The complexity of this solution:

    • Time complexity: O(n^3).
    • Space complexity: O(1).

  2. Expand Around Center: At each character currently, we will expand both left and right side to check this substring is palindrome or not.

    Below is the source code of this problem.

     private static int lo;
 private static int maxLen;

 public static String longestPalindrome(String s) {
 int len = s.length();
     if (len < 2) {
         return s;
     }

     for (int i = 0; i < len - 1; i++) {
         makePalindrome(s, i, i);
         makePalindrome(s, i, i + 1);
     }

     return s.substring(lo, lo + maxLen);
 }

 public static void makePalindrome(String s, int j, int k) {
     while (j >= 0 && k < s.length() && s.charAt(j) == s.charAt(k)) {
         j--;
         k++;
     }

     if (maxLen < k - j - 1) {
         lo = j + 1;
         maxLen = k - j - 1;
     }
 }

    The complexity of this solution:

    • Time complexity: O(n^2).
    • Space complexity: O(1).

Beside using Brute Force solution, there are some other solutions:

  • Dynamic Programming.
  • Manacher Algorithm.


When to use

  • In interview, we should always start from the brute force algorithm. Then, identify some problems of this solution, and optimize it.

  • When we want to find all possible results of this problem.


Benefits and Drawbacks

  1. Benefits

    • simple to implement

  2. Drawbacks

    • Normally, it’s not efficiency


Wrapping up

  • Understanding some above ways to apply brute force in our problem.


Refer:

https://medium.com/@chyanpin/solving-leetcodes-longest-palindrome-substring-challenge-60eaffd7929a