Category: Algorithms

In mathematics and computer science, an algorithm is a finite sequence of well-defined, computer-implementable instructions, typically to solve a class of problems or to perform a computation. Algorithms are always unambiguous and are used as specifications for performing calculations, data processing, automated reasoning, and other tasks.

Remove Duplicates from Sorted Array
06
Feb
2021

Remove Duplicates from Sorted Array

Remove Duplicates from Sorted Array

Given a sorted array, remove the duplicates from the array in-place such that each element appears only once, and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example

Given array [1, 1, 1, 3, 5, 5, 7]

The output should be 4, with the first four elements of the array being [1, 3, 5, 7]

Remove Duplicates from Sorted Array solution in Java

Given that the array is sorted, all the duplicate elements will appear together.

We can solve the problem in O(n) time complexity by using two pointer sliding window pattern. We’ll keep two pointers (indexes) –

  • One index i, to iterate over the array, and
  • Another index j, to keep track of the number of unique elements found so far. This index will move only when we modify the array in-place to include a new non-duplicate element.
class RemoveDuplicatesSortedArray {

  private static int removeDuplicates(int[] nums) {
    int n = nums.length;

    /*
     * This index will move only when we modify the array in-place to include a new
     * non-duplicate element.
     */
    int j = 0;

    for (int i = 0; i < n; i++) {
      /*
       * If the current element is equal to the next element, then skip the current
       * element because it's a duplicate.
       */
      if (i < n - 1 && nums[i] == nums[i + 1]) {
        continue;
      }

      nums[j++] = nums[i];
    }

    return j;
  }

  public static void main(String[] args) {
    int[] nums = new int[] { 1, 1, 1, 3, 5, 5, 7 };
    int newLength = removeDuplicates(nums);

    System.out.println("Length of array after removing duplicates = " + newLength);

    System.out.print("Array = ");
    for (int i = 0; i < newLength; i++) {
      System.out.print(nums[i] + " ");
    }
    System.out.println();
  }
}
# Output
Length of array after removing duplicates = 4
Array = 1 3 5 7 

Liked the Article? Share it on Social media!

Build A Web Crawler with Java
02
Jan
2022

Build A Web Crawler with Java

Creating a web crawler is a smart way of retrieving useful information available online. With a web crawler, you can scan the Internet, browse through individual websites, and analyze and extract their content.

The Java programming language provides a simple way of building a web crawler and harvesting data from websites. You can use the extracted data for various use cases, such as for analytical purposes, providing a service that uses third-party data, or generating statistical data.

In this article, we’ll walk you through the process of building a web crawler using Java and ProxyCrawl.

What you’ll need

Typically, crawling web data involves creating a script that sends a request to the targeted web page, accesses its underlying HTML code, and scrapes the required information.

To accomplish that objective, you’ll need the following:

Before we develop the crawling logic, let’s clear the air why using ProxyCrawl is important for web crawling.

Why use ProxyCrawl for Crawling

ProxyCrawl is a powerful data crawling and scraping tool you can use to harvest information from websites fast and easily.

Here are some reasons why you should use it for crawling online data:

  • Easy to use It comes with a simple API that you can set up quickly without any programming hurdles. With just a few lines of code, you can start using the API to crawl websites and retrieve their content.
  • Supports advanced crawling ProxyCrawl allows you to perform advanced web crawling and scrape data from complicated websites. Since it supports JavaScript rendering, ProxyCrawl lets you extract data from dynamic websites. It offers a headless browser that allows you to extract what real users see on their web browsers—even if a site is created using modern frameworks like Angular or React.js.
  • Bypass crawling obstacles ProxyCrawl can handle all the restrictions often associated with crawling online data. It has an extensive network of proxies as well as more than 17 data centers around the world. You can use it to avoid access restrictions, resolve CAPTCHAs, and evade other anti-scraping measures implemented by web applications. What’s more, you can crawl websites while remaining anonymous; you’ll not worry about exposing your identity.
  • Free trial account You can test how ProxyCrawl works without giving out your payment details. The free account comes with 1,000 credits for trying out the tool’s capabilities.

How ProxyCrawl Works

ProxyCrawl provides the Crawling API for crawling and scraping data from websites. You can easily integrate the API in your Java development project and retrieve information from web pages smoothly.

Each request made to the Crawling API starts with the following base part:

https://api.proxycrawl.com

Also, you’ll need to add the following mandatory parameters to the API:

  • Authentication token
  • URL

The authentication token is a unique token that authorizes you to use the Crawling API. Once you sign up for an account, ProxyCrawl will give you two types of tokens:

  • Normal token This is for making generic crawling requests.
  • JavaScript token This is for crawling dynamic websites. It provides you with headless browser capabilities for crawling web pages rendered using JavaScript. As pointed out earlier, it’s a useful way of crawling advanced websites.

Here is how to add the authentication token to your API request:

https://api.proxycrawl.com/?token=INSERT_TOKEN

The second mandatory parameter is the URL to crawl. It should start with HTTP or HTTPS, and be completely encoded. Encoding converts the URL string into a format that can be transferred over the Internet validly and easily.

Here is how to insert the URL to your API request:

https://api.proxycrawl.com/?token=INSERT_TOKEN&url=INSERT_URL

If you run the above line—for example, on your terminal using cURL or pasting it on a browser’s address bar—it’ll execute the API request and return the entire HTML source code of the targeted web page.

It’s that easy and simple!

If you want to perform advanced crawling, you may add other parameters to the API request. For example, when using the JavaScript token, you can add the page_wait parameter to instruct the browser to wait for the specified number of milliseconds before the resulting HTML code is captured.

Here is an example:

https://api.proxycrawl.com/?token=INSERT_TOKEN&page_wait=1000&url=INSERT_URL

Building a Web Crawler in Java and ProxyCrawl

In this Java web crawling tutorial, we’ll use the HttpClient API to create the crawling logic. The API was introduced in Java 11, and it comes with lots of useful features for sending requests and retrieving their responses.

The HttpClient API supports both HTTP/1.1 and HTTP/2. By default, it uses the HTTP/2 protocol to send requests. If a request is sent to a server that does not already support HTTP/2, it will automatically be downgraded to HTTP/1.

Furthermore, its requests can be sent asynchronously or synchronously, it handles requests and response bodies as reactive-streams, and uses the common builder pattern.

The API is comprised of three core classes:

  • HttpRequest
  • HttpClient
  • HttpResponse

Let’s talk about each of them in more detail.

1. HttpRequest

The HttpRequest, as the name implies, is an object encapsulating the HTTP request to be sent. To create new instances of HttpRequest, call HttpRequest.newBuilder(). After it has been created, the request is immutable and can be sent multiple times.

The Builder class comes with different methods for configuring the request.

These are the most common methods:

  • URI method
  • Request method
  • Protocol version method
  • Timeout method

Let’s talk about each of them in more detail.

a) URI method

The first thing to do when configuring the request is to set the URL to crawl. We can do so by calling the uri() method on the Builder instance. We’ll also use the URI.create() method to create the URI by parsing the string of the URL we intend to crawl.

Here is the code:

String url =
URLEncoder.encode(“https://www.forextradingbig.com/7-reasons-why-you-should
-quit-forex-trading/”, StandardCharsets.UTF_8.name());

HttpRequest request = HttpRequest.newBuilder()
.uri(URI.create(“https://api.proxycrawl.com/?token=INSERT_TOKEN&url=”
+ url))

Notice that we provided the URL string using ProxyCrawl’s settings. This is the web page we intend to scrape its contents.

We also encoded the URL using the Java URLEncoder class. As earlier mentioned, ProxyCrawl requires URLs to be encoded.

b) Request method

The next thing to do is to specify the HTTP method to be used for making the request. We can call any of the following methods from Builder:

  • GET()
  • POST()
  • PUT()
  • DELETE()

In this case, since we want to request data from the target web page, we’ll use the GET() method.

Here is the code:

HttpRequest request = HttpRequest.newBuilder()
.GET()

So far, HttpRequest has all the parameters that should be passed to HttpClient. However, you may need to include other parameters, such as the HTTP protocol version and timeout.

Let’s see how you can add the additional parameters.

c) Protocol version method

As earlier mentioned, the HttpClient API uses the HTTP/2 protocol by default. Nonetheless, you can specify the version of the HTTP protocol you want to use.

Here is the code:

HttpRequest request = HttpRequest.newBuilder()
.version(HttpClient.Version.HTTP_2)

d) Timeout method

You can set the amount of time to wait before a response is received. Once the defined period expires, an HttpTimeoutException will be thrown. By default, the timeout is set to infinity.

You can define timeout by calling the timeout() method on the builder instance. You’ll also need to pass the Duration object to specify the amount of time to wait.

Here is the code:

HttpRequest request = HttpRequest.newBuilder()
.timeout(Duration.ofSeconds(20))

2. HttpClient

The HttpClient class is the main entry point of the API—it acts as a container for the configuration details shared among multiple requests. It is the HTTP client used for sending requests and receiving responses.

You can call either the HttpClient.newBuilder() or the HttpClient.newHttpClient() method to instantiate it. After an instance of the HttpClient has been created, it’s immutable.

The HttpClient class offers several helpful and self-describing methods you can use when working with requests and responses.

These are some things you can do:

  • Set protocol version
  • Set redirect policy
  • Send synchronous and asynchronous requests

Let’s talk about each of them in more detail.

a) Set protocol version

As earlier mentioned, the HttpClient class uses the HTTP/2 protocol by default. However, you can set your preferred protocol version, either HTTP/1.1 or HTTP/2.

Here is an example:

HttpClient client = HttpClient.newBuilder()
.version(Version.HTTP_1_1)

b) Set redirect policy

If the targeted web page has moved to a different address, you’ll get a 3xx HTTP status code. Since the address of the new URI is usually provided with the status code information, setting the correct redirect policy can make HttpClient forward the request automatically to the new location.

You can set it by using the followRedirects() method on the Builder instance.

Here is an example:

HttpClient client = HttpClient.newBuilder()
.followRedirects(Redirect.NORMAL)

c) Send synchronous and asynchronous requests

HttpClient supports two ways of sending requests:

  • Synchronously by using the send() method. This blocks the client until the response is received, before continuing with the rest of the execution.

Here is an example:

HttpResponse<String> response = client.send(request,
BodyHandlers.ofString());

Note that we used BodyHandlers and called the ofString() method to return the HTML response as a string.

  • Asynchronously by using the sendAsync() method. This does not wait for the response to be received; it’s non-blocking. Once the sendAsync() method is called, it returns instantly with a CompletableFuture< HttpResponse >, which finalizes once the response is received. The returned CompletableFuture can be joined using various techniques to define dependencies among varied asynchronous tasks.

Here is an example:

CompletableFuture<HttpResponse<String>> response = HttpClient.newBuilder()
.sendAsync(request, HttpResponse.BodyHandler.ofString());

3. HttpResponse

The HttpResponse, as the name implies, represents the response received after sending an HttpRequest. HttpResponse offers different helpful methods for handling the received response.

These are the most important methods:

  • statusCode() This method returns the status code of the response. It’s of int type
  • Body() This method returns a body for the response. The return type is based on the kind of response BodyHandler parameter that is passed to the send() method.

Here is an example:

// Handling the response body as a String
HttpResponse<String> response = client
.send(request, BodyHandlers.ofString());

// Printing response body
System.out.println(response.body());

// Printing status code
System.out.println(response.statusCode());
// Handling the response body as a file
HttpResponse<Path> response = client
.send(request, BodyHandlers.ofFile(Paths.get(“myexample.html”)));

Synchronous Example

Here is an example that uses the HttpClient synchronous method to crawl a web page and output its content:

package javaHttpClient;

import java.io.IOException;
import java.net.URI;
import java.net.URLEncoder;
import java.net.http.HttpClient;
import java.net.http.HttpRequest;
import java.net.http.HttpResponse;
import java.net.http.HttpResponse.BodyHandlers;
import java.nio.charset.StandardCharsets;

public class SyncExample {

public static void main(String[] args) throws IOException, InterruptedException {

// Encoding the URL
String url = URLEncoder.encode(“https://www.forextradingbig.com/7-reasons-why-you-should-quit-forex-trading/”, StandardCharsets.UTF_8.name());

// Instantiating HttpClient
HttpClient client = HttpClient.newHttpClient();

// Configuring HttpRequest
HttpRequest request = HttpRequest.newBuilder()
.GET()
.uri(URI.create(“https://api.proxycrawl.com/?token=INSERT_TOKEN&url=” + url))
.build();

// Handling the response
HttpResponse<String> response = client.send(request, BodyHandlers.ofString());
System.out.println(response.body());
}

}

Here is the output:

Asynchronous Example

When using the HttpClient asynchronous method to crawl a web page, the sendAsync() method is called, instead of send().

Here is an example:

package javaHttpClient;

import java.io.IOException;
import java.net.URI;
import java.net.URLEncoder;
import java.net.http.HttpClient;
import java.net.http.HttpRequest;
import java.net.http.HttpResponse;
import java.nio.charset.StandardCharsets;
import java.util.concurrent.CompletableFuture;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.TimeoutException;

public class AsyncExample {


public static void main(String[] args) throws IOException, InterruptedException, ExecutionException, TimeoutException {

// Encoding the URL
String url = URLEncoder.encode(“https://www.forextradingbig.com/7-reasons-why-you-should-quit-forex-trading/”, StandardCharsets.UTF_8.name());

// Instantiating HttpClient
HttpClient client = HttpClient.newHttpClient();

// Configuring HttpRequest
HttpRequest request = HttpRequest.newBuilder()
.GET()
.version(HttpClient.Version.HTTP_2)
.uri(URI.create(“https://api.proxycrawl.com/?token=INSERT_TOKEN&url=” + url))
.build();

// Handling the response
CompletableFuture<HttpResponse<String>> response =
client.sendAsync(request, HttpResponse.BodyHandlers.ofString());

String result = response.thenApply(HttpResponse::body).get(5, TimeUnit.SECONDS);

System.out.println(result);

}

}

Conclusion

That’s how to build a web crawler in Java. The HttpClient API, which was introduced in Java 11, makes it easy to send and handle responses from a server.

And if the API is combined with a versatile tool like ProxyCrawl, it can make web crawling tasks smooth and rewarding.

With ProxyCrawl, you can create a scraper that can help you to retrieve information from websites anonymously and without worrying about being blocked.

It’s the tool you need to take your crawling efforts to the next level.

Click here to create a free ProxyCrawl account.

Happy scraping!

Three Number Sum Solution
06
Feb
2021

Three Number Sum Solution

Three Number Sum Problem Statement

Given an array of integers, find all triplets in the array that sum up to a given target value.

In other words, given an array arr and a target value target, return all triplets a, b, c such that a + b + c = target.

Example:

Input array: [7, 12, 3, 1, 2, -6, 5, -8, 6]
Target sum: 0

Output: [[2, -8, 6], [3, 5, -8], [1, -6, 5]]

Three Number Sum Problem solution in Java

METHOD 1. Naive approach: Use three for loops

The naive approach is to just use three nested for loops and check if the sum of any three elements in the array is equal to the given target.

Time complexity: O(n^3)

import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;

class ThreeSum {

  // Time complexity: O(n^3)
  private static List<Integer[]> findThreeSum_BruteForce(int[] nums, int target) {
    List<Integer[]> result = new ArrayList<>();
    for (int i = 0; i < nums.length; i++) {
      for (int j = i + 1; j < nums.length; j++) {
        for (int k = j + 1; k < nums.length; k++) {
          if (nums[i] + nums[j] + nums[k] == target) {
            result.add(new Integer[] { nums[i], nums[j], nums[k] });
          }
        }
      }
    }
    return result;
  }

  public static void main(String[] args) {
    Scanner keyboard = new Scanner(System.in);

    int n = keyboard.nextInt();
    int[] nums = new int[n];

    for (int i = 0; i < n; i++) {
      nums[i] = keyboard.nextInt();
    }
    int target = keyboard.nextInt();

    keyboard.close();

    List<Integer[]> result = findThreeSum_Sorting(nums, target);

    for(Integer[] triplets: result) {
      for(int num: triplets) {
        System.out.print(num + " ");
      }
      System.out.println();
    }
  }
}

METHOD 2. Use Sorting along with the two-pointer sliding window approach

Another approach is to first sort the array, then –

  • Iterate through each element of the array and for every iteration,
    • Fix the first element (nums[i])
    • Try to find the other two elements whose sum along with nums[i] gives target. This boils down to the two sum problem.

Time complexity: O(n^2)

import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;

class ThreeSum {

  // Time complexity: O(n^2)
  private static List<Integer[]> findThreeSum_Sorting(int[] nums, int target) {
    List<Integer[]> result = new ArrayList<>();
    Arrays.sort(nums);
    for (int i = 0; i < nums.length; i++) {
      int left = i + 1;
      int right = nums.length - 1;
      while (left < right) {
        if (nums[i] + nums[left] + nums[right] == target) {
          result.add(new Integer[] { nums[i], nums[left], nums[right] });
          left++;
          right--;
        } else if (nums[i] + nums[left] + nums[right] < target) {
          left++;
        } else {
          right--;
        }
      }
    }
    return result;
  }
}

METHOD 3. Use a Map/Set

Finally, you can also solve the problem using a Map/Set. You just need to iterate through the array, fix the first element, and then try to find the other two elements using the approach similar to the two sum problem.

I’m using a Set in the following solution instead of a Map as used in the two-sum problem because in the two-sum problem, we had to keep track of the index of the elements as well. But In this problem, we just care about the element and not its index.

Time complexity: O(n^2)

import java.util.Set;
import java.util.Scanner;
import java.util.HashSet;

class ThreeSum {

  // Time complexity: O(n^2)
  private static List<Integer[]> findThreeSum(int[] nums, int target) {
    List<Integer[]> result = new ArrayList<>();
    for (int i = 0; i < nums.length; i++) {
      int currentTarget = target - nums[i];
      Set<Integer> existingNums = new HashSet<>();
      for (int j = i + 1; j < nums.length; j++) {
        if (existingNums.contains(currentTarget - nums[j])) {
          result.add(new Integer[] { nums[i], nums[j], currentTarget - nums[j] });
        } else {
          existingNums.add(nums[j]);
        }
      }
    }
    return result;
  }
}

Liked the Article? Share it on Social media!

Two Number Sum Problem Solution
06
Feb
2021

Two Number Sum Problem Solution

Two Number Sum Problem Statement

Given an array of integers, return the indices of the two numbers whose sum is equal to a given target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9.

The output should be [0, 1]. 
Because nums[0] + nums[1] = 2 + 7 = 9.

Two Number Sum Problem solution in Java

METHOD 1. Naive approach: Use two for loops

The naive approach is to just use two nested for loops and check if the sum of any two elements in the array is equal to the given target.

Time complexity: O(n^2)

import java.util.HashMap;
import java.util.Scanner;
import java.util.Map;

class TwoSum {

    // Time complexity: O(n^2)
    private static int[] findTwoSum_BruteForce(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[] { i, j };
                }
            }
        }
        return new int[] {};
    }


    public static void main(String[] args) {
        Scanner keyboard = new Scanner(System.in);

        int n = keyboard.nextInt();
        int[] nums = new int[n];

        for(int i = 0; i < n; i++) {
            nums[i] = keyboard.nextInt();
        }
        int target = keyboard.nextInt();

        keyboard.close();

        int[] indices = findTwoSum_BruteForce(nums, target);

        if (indices.length == 2) {
            System.out.println(indices[0] + " " + indices[1]);
        } else {
            System.out.println("No solution found!");
        }
    }
}
# Output
$ javac TwoSum.java
$ java TwoSum
4 2 7 11 15
9
0 1

METHOD 2. Use a HashMap (Most efficient)

You can use a HashMap to solve the problem in O(n) time complexity. Here are the steps:

  1. Initialize an empty HashMap.
  2. Iterate over the elements of the array.
  3. For every element in the array –
    • If the element exists in the Map, then check if it’s complement (target - element) also exists in the Map or not. If the complement exists then return the indices of the current element and the complement.
    • Otherwise, put the element in the Map, and move to the next iteration.

Time complexity: O(n)

import java.util.HashMap;
import java.util.Scanner;
import java.util.Map;

class TwoSum {
    
    // Time complexity: O(n)
    private static int[] findTwoSum(int[] nums, int target) {
        Map<Integer, Integer> numMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (numMap.containsKey(complement)) {
                return new int[] { numMap.get(complement), i };
            } else {
                numMap.put(nums[i], i);
            }
        }
        return new int[] {};
    }
}

METHOD 3. Use Sorting along with the two-pointer sliding window approach

There is another approach which works when you need to return the numbers instead of their indexes. Here is how it works:

  1. Sort the array.
  2. Initialize two variables, one pointing to the beginning of the array (left) and another pointing to the end of the array (right).
  3. Loop until left < right, and for each iteration
    • if arr[left] + arr[right] == target, then return the indices.
    • if arr[left] + arr[right] < target, increment the left index.
    • else, decrement the right index.

This approach is called the two-pointer sliding window approach. It is a very common pattern for solving array related problems.

Time complexity: O(n*log(n))

import java.util.Scanner;
import java.util.Arrays;

class TwoSum {

    // Time complexity: O(n*log(n))
    private static int[] findTwoSum_Sorting(int[] nums, int target) {
        Arrays.sort(nums);
        int left = 0;
        int right = nums.length - 1;
        while(left < right) {
            if(nums[left] + nums[right] == target) {
                return new int[] {nums[left], nums[right]};
            } else if (nums[left] + nums[right] < target) {
                left++;
            } else {
                right--;
            }
        }
        return new int[] {};
    }
}

Liked the Article? Share it on Social media!

Maximum Contiguous Subarray Sum
06
Feb
2021

Maximum Contiguous Subarray Sum

Maximum Contiguous Subarray Sum problem statement

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

Example:

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

Maximum Contiguous Subarray Sum solution in Java

This problem can be solved using Kadane’s algorithm in O(n) time complexity.

The algorithm iterates over all the elements of the array (nums) and computes the maximum sum ending at every index (maxEndingHere). Here is how maxEndingHere is calculated:

  • Initialize maxEndingHere to nums[0]
  • Iterate through the array (1..n). For every iteration:
    • If maxEndingHere + nums[i] < nums[i], that means the previous max was negative and therefore we reset maxEndingHere to nums[i].
    • Otherwise, we set maxEndingHere = maxEndingHere + nums[i]
  • We also keep a variable maxSoFar which indicates the maximum sum found so far. And, with every iteration, we check if the current max (maxEndingHere) is greater than maxSoFar. If yes, then we update the value of maxSoFar.

Here is the complete solution:

import java.util.Scanner;

class MaximumSubarray {

  private static int findMaxSubarraySum(int[] nums) {
    int n = nums.length;
    int maxSoFar = nums[0];
    int maxEndingHere = nums[0];

    for(int i = 1; i < n; i++) {
      if(maxEndingHere + nums[i] < nums[i]) {
        maxEndingHere = nums[i];
      } else {
        maxEndingHere = maxEndingHere + nums[i];
      }

      if(maxEndingHere > maxSoFar) {
        maxSoFar = maxEndingHere;
      }
    }
    return maxSoFar;
  }

  public static void main(String[] args) {
    Scanner keyboard = new Scanner(System.in);
    int n = keyboard.nextInt();
    int[] nums = new int[n];
    for(int i = 0; i < n; i++) {
      nums[i] = keyboard.nextInt();
    }

    System.out.println(findMaxSubarraySum(nums));
  }
}
# Output
$ javac MaximumSubarray.java
$ java MaximumSubarray
9 -2 1 -3 4 -1 2 1 -5 4
6

Maximum Contiguous Subarray with Indices

It’s also possible to find out the start and end indices of the maximum contiguous subarray. Here is a modification of the above program which does that and prints the subarray –

import java.util.Scanner;

class MaximumSubarray {

  private static int[] findMaxSubarrayIndices(int[] nums) {
    int n = nums.length;
    int maxSoFar = nums[0];
    int maxEndingHere = nums[0];
    int currentStart = 0, maxStart = 0, maxEnd = 0;

    for(int i = 1; i < n; i++) {
      if(maxEndingHere + nums[i] < nums[i]) {
        maxEndingHere = nums[i];
        currentStart = i;
      } else {
        maxEndingHere = maxEndingHere + nums[i];
      }

      if(maxEndingHere > maxSoFar) {
        maxSoFar = maxEndingHere;
        maxStart = currentStart;
        maxEnd = i;
      }
    }

    return new int[]{maxStart, maxEnd};
  }

  public static void main(String[] args) {
    Scanner keyboard = new Scanner(System.in);
    int n = keyboard.nextInt();
    int[] nums = new int[n];
    for(int i = 0; i < n; i++) {
      nums[i] = keyboard.nextInt();
    }

    int[] indices = findMaxSubarrayIndices(nums);
    int sum = 0;
    System.out.print("Max contiguous subarray: ");
    for(int i = indices[0]; i <= indices[1]; i++) {
      System.out.print(nums[i] + " ");
      sum += nums[i];
    }
    System.out.println();
    System.out.println("Max contiguous subarray sum: " + sum);
  }
}
# Output
$ javac MaximumSubarray.java
$ java MaximumSubarray
9 -2 1 -3 4 -1 2 1 -5 4
Max contiguous subarray: 4 -1 2 1
Max contiguous subarray sum: 6
Remove Duplicates from Sorted Array II
06
Feb
2021

Remove Duplicates from Sorted Array II

Remove Duplicates from Sorted Array II

Given a sorted array, remove the duplicates from the array in-place such that each element appears at most twice, and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example

Given array [1, 1, 1, 3, 5, 5, 7]

The output should be 6, with the first six elements of the array being [1, 1, 3, 5, 5, 7]

Remove Duplicates from Sorted Array II solution in Java

It can also be solved in O(n) time complexity by using two pointers (indexes).

class RemoveDuplicatesSortedArrayII {
  private static int removeDuplicates(int[] nums) {
    int n = nums.length;

    /*
     * This index will move when we modify the array in-place to include an element
     * so that it is not repeated more than twice.
     */
    int j = 0;

    for (int i = 0; i < n; i++) {
      /*
       * If the current element is equal to the element at index i+2, then skip the
       * current element because it is repeated more than twice.
       */
      if (i < n - 2 && nums[i] == nums[i + 2]) {
        continue;
      }

      nums[j++] = nums[i];
    }

    return j;
  }

  public static void main(String[] args) {
    int[] nums = new int[] { 1, 1, 1, 3, 5, 5, 7 };
    int newLength = removeDuplicates(nums);

    System.out.println("Length of array after removing duplicates = " + newLength);

    System.out.print("Array = ");
    for (int i = 0; i < newLength; i++) {
      System.out.print(nums[i] + " ");
    }
    System.out.println();
  }
}
# Output
Length of array after removing duplicates = 6
Array = 1 1 3 5 5 7 
Understanding Regular Expressions
18
Mar
2021

Understanding Regular Expressions

it’s time to get over your fears of regular expressions(regex)! If you’re like me, you’ve heard of regex but have always been confused by the cryptic syntax. Fear not, because in the next 5 minutes, you’ll have a basic understanding of what’s going on and how to use RegEx to make your life easier!

So what are Regular Expressions ?

Basically, regular expressions are patterns that you can use to find matching patterns in strings. This could be useful for password validation, or checking if the formatting of input fields is correct, or perhaps you want to parse a phone number, etc…

How do you use them?

There are a couple ways of creating a regex, you can either use the literal version( which I prefer) or you can use the constructor option. The literal version looks like so:

const regEx = /hello/;

When making a regular expression literal, you place the pattern between two forward slashes. Above, we would be searching for the word ‘hello’.

Using the constructor would look something like this:

 const regEx = new RegExp('hello');

I’m not the biggest fan of this, so moving forward I will only be using the literal version.

Testing Methods

How do you test your regex anyways? JavaScript provides us a couple of methods that are compatible with regular expressions:

  • test()
  • exec()
  • match()
  • matchAll()
  • replace()
  • search()
  • split()

For my examples I will primarily be using test() and match(). Test is a RegExp method used to search a string and return either true or false if your pattern is found, and match is a string method that can use regex and returns the instances found in an array.

How to Match Strings

As you saw in my example above, I created the regex /hello/. This pattern would be useful for finding the first case sensitive instance of ‘hello’. What if you want to find every instance of ‘hello’, case insensitive? This is where ‘flags’ come in.

Flags act as modifiers to your regular expression. They go after the closing slash and there are five native flags in JavaScript!

  • i : This makes your search case-insensitive!
  • g : This flag tells your search to look for all matches, not just the first one.
  • m : Multiline mode
  • s : This enables “dotall” mode. It allows ‘.’ to match newlines
  • u : Enables full unicode support
  • y : sticky; it matches only from the index indicated by the lastIndex property of the regex in the target string.

So if we wanted to find every instance of ‘hello’ case insensitive, in the string “Hello heLLO hellO HELLO!”, we would do something like this:

let regex = /hello/gi;
let string = “Hello heLLO hellO HELLO!”;
string.match(regex);//returns [ 'Hello', 'heLLO', 'hellO', 'HELLO' ]

See that’s not so bad! Let’s look at another tool that’s very useful: character classes.

Character Classes

Character classes let you match a group of characters by placing them inside square brackets! This lets you find multiple matches with different characters. For example: if you wanted to find the words ‘big’, ‘bag’, ‘bog’, ‘bug’ in the string “The big bug crawled out of my bag and went into the bog.” you could use a simple regular expression to do so!

let string = “The big bug crawled out of my bag and went into the bog.”;let regex = /b[aiou]g/gi;
string.match(regex);//returns [ 'big', 'bug', 'bag', 'bog' ]

That’s pretty cool. You can also search for a range of characters inside of a character set using a hyphen ‘-’! For example, if I wanted to find every number in a string for some reason, I could do something like this:

let string = "I want 6 chocolates, 5 pop tarts, and 3 pumpkin pies please."let regex = /[0-9]/g;
string.match(regex);//returns [ '6', '5', '3' ]

You can do the above and so, so much more using Regular Expressions. You’ll find it’s basically like another language! This is just the tip of the iceberg, and I hope at least I’ve made regex a little less scary. There is so much more to regular expressions than I can cover here, but there are plenty of great resources to continue learning.

Happy Coding!

Find the pair with the smallest difference in two unsorted arrays
06
Feb
2021

Find the pair with the smallest difference in two unsorted arrays

Given two non-empty arrays of integers, find the pair of values (one value from each array) with the smallest (non-negative) difference.

Example

Input: [1, 3, 15, 11, 2], [23, 127, 235, 19, 8]

Output: [11, 8]; this pair has the smallest difference.

Solution 1. Brute Force approach: Use two for loops

The naive way to solve this problem is to use two for loops and compare the difference of every pair to find the pair with the smallest difference:

Time complexity: O(n^2)

import java.util.Arrays;

class SmallestDifference {

  public static int[] findSmallestDifferencePair_Naive(int[] a1, int[] a2) {
    double smallestDiff = Double.MAX_VALUE;
    int[] smallestDiffPair = new int[2];

    for(int i = 0; i < a1.length; i++) {
      for(int j = 0; j < a2.length; j++) {
        int currentDiff = Math.abs(a1[i] - a2[j]);
        if(currentDiff < smallestDiff) {
          smallestDiff = currentDiff;
          smallestDiffPair[0] = a1[i];
          smallestDiffPair[1] = a2[j];  
        }
      }
    }
    return smallestDiffPair;
  }

  public static void main(String[] args) {
    int[] a1 = new int[] {-1, 5, 10, 20, 28, 3};
    int[] a2 = new int[] {26, 134, 135, 15, 17};

    int[] pair = findSmallestDifferencePair_Naive(a1, a2);
    System.out.println(pair[0] + " " + pair[1]);
  }
}

Solution 2. Use Sorting along with the two-pointer sliding window approach

You can improve upon the brute force solution by first sorting the array and then using the two-pointer sliding window pattern.

Here is how it will work in this case:

  • Initialize a variable to keep track of the smallest difference found so far (smallestDiff).
  • Sort both the arrays
  • Initialize two indexes (one for each array): i = 0 and j = 0.
  • Loop until we reach the end of any of the arrays.
  • For every iteration:
    • Compare the smallestDiff with abs(a1[i] - a2[j]) and reset it if the new difference is smaller.
    • If a1[i] < a2[j], increment i.
    • Otherwise, increment j

Time complexity: O(mlog(m) + nlog(n))

import java.util.Arrays;

class SmallestDifference {
  public static int[] findSmallestDifferencePair(int[] a1, int[] a2) {
    Arrays.sort(a1);
    Arrays.sort(a2);

    double smallestDiff = Double.MAX_VALUE;
    int[] smallestDiffPair = new int[2];
    int i = 0, j = 0;

    while(i < a1.length && j < a2.length) {
      double currentDiff = Math.abs(a1[i] - a2[j]);
      if(currentDiff < smallestDiff) {
        smallestDiff = currentDiff;
        smallestDiffPair[0] = a1[i];
        smallestDiffPair[1] = a2[j];
      }
      if(a1[i] < a2[j]) {
        i++;
      } else {
        j++;
      }
    }
    return smallestDiffPair;
  }

  public static void main(String[] args) {
    int[] a1 = new int[] {-1, 5, 10, 20, 28, 3};
    int[] a2 = new int[] {26, 134, 135, 15, 17};

    int[] pair = findSmallestDifferencePair(a1, a2);
    System.out.println(pair[0] + " " + pair[1]);
  }
}

Liked the Article? Share it on Social media!