Entry Into the World of DSA Problem Solving

Photo Credit: WilliamFiset

Introduction

DSA stands for Data Structures and Algorithms, two fundamental things in the art of programming. To understand their importance, we must explain their definitions:

A data structure is a specific way of storing and organizing data. All data structures are designed to arrange data in a certain way to fulfill a specific purpose. Not only do they make it easier for the user to work with the data, but more importantly, data structures organize the data in a way that allows the user to better understand it.

An algorithm is a set of well-defined instructions that are used to solve a problem. A range of inputs is sent into the algorithm, producing the desired output. One of the simplest examples would be the algorithm to add two numbers entered by the user which goes as follows:

1. Start
2. Declare the variables: num1, num2, and sum
3. Take in inputs for num1 and num2
4. Add num1 and num2 using the addition operator and assign the value to sum
5. Output the sum value
6. Stop

HashMaps

Photo Credit: khalilstemmler.com

These two terms are often used in conjunction because data structures play a critical role in algorithm design. In this lesson, the data structure we will be using is the HashMap in Java.

HashMap<K, V> is a part of Java’s collection since Java 1.2. This class is found in java.util package.

It provides the basic implementation of the Map interface of Java. It stores the data in (Key, Value) pairs, and you can access them by an index of another type (e.g. an Integer).

One object is used as a key (index) to another object (value). If you try to insert the duplicate key, it will replace the element of the corresponding key. — geeksforgeeks.org

The Challenge

In this lesson, we will be tackling the famous LeetCode problem: Contains Duplicate.

In this problem, we have an integer array as an input and we want to return True if any value appears more than once in the array. If every element in the array is distinct, we return False.

The constraints of the problem are:

Constraints:
1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9

Here are some examples of the input that will be received and the desired output:

Example 1:

Input: nums = [1,2,3,1]
Output: true

Example 2:

Input: nums = [1,2,3,4]
Output: false

Example 3:

Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true

Our Approach

Since we are using a HashSet, we will only have to traverse the array one time which will give an optimal solution of O(n) time complexity and O(n) space complexity.

The thought process is to create an empty HashMap which will take in an Integer as a key and an Integer as a value. We will then iterate over the input array and check to see if the Integer at the current index is in the HashMap. If the value is indeed already in the HashMap, we will return True, as we have found a duplicate. If the value is not found in the HashMap, we will add the value into the HashMap with the key being the Integer and the value being 1. If the loop reaches the end without returning True, we will return False as no duplicate has been found.

Here is the code of the solution described:

class Solution {
    public boolean containsDuplicate(int[] nums) {
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i=0; i<nums.length; i++) {
            if (map.containsKey(nums[i])) {
                return true;
            } else {
                map.put(nums[i],1);
            }
        }
        return false;
    }
}

Closing

Today we entered the world of Data Structures and Algorithms problems, so now it is your turn to take a deep dive and explore the various data structures by practicing more problems!

Was this walkthrough helpful? Confusing? If you have any questions feel free to comment below! Make sure to follow if you’re interested in similar content and want to keep learning alongside me!