DEV Community: Asad Ullah

How to solve LeetCode problem about finding all duplicates in an array

Asad Ullah — Sun, 30 Apr 2023 10:29:00 +0000

Introduction

In this article, we will discuss the solution to LeetCode problem #422 — "Find All Duplicates in an Array" using JavaScript. The problem statement requires us to find all the elements that appear twice in a given array. The constraints require us to solve the problem in O(n) time and use only constant extra space. We will start by discussing the problem in detail and then move on to the approach we can take to solve it efficiently.

Problem Statement

Given an integer array nums of length n where all the integers of nums are in the range [1, n] and each integer appears once or twice, return an array of all the integers that appear twice.

Example 1:

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

Example 2:

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

Example 3:

Input: nums = [1] Output: []

Constraints:

n == nums.length
1 <= n <= 105
1 <= nums[i] <= n
Each element in nums appears once or twice.

Approach:

To detect duplicates, we just need to track the items which have already occurred. There can be two solutions:

One can be brute force with a nested loop. We can start from the first element in the iteration, and then compare it against all the entries in the array to see if it has a duplicated value or not.
- This approach will have a time complexity of O(n^2).
- If we revisit our understanding of the data structures, we know that array has an O(n) time complexity of lookup operation, hence each iteration of the first loop will do a lookup which will result in O(n^2).
We need to somehow eliminate the second loop. There is another data structure in the form of Objects/Key-value pairs in JS which have some characteristics of a hash map primarily a constant time lookup operation. That is what we need to eliminate nested iteration. Hence we use an object to track the duplicate and its constant lookup operation gives us an O(n) time complexity for the solution.

To solve the given problem, we will create a hash map to store the frequency of elements of the input array. We will iterate through each element in the input array and add its frequency to the hash map. If the frequency is already present in the hash map, then the element is a duplicate and we can add it to the duplicates array.

/**
* returns duplicates from an array
*/

function findDuplicates(inputArray) {
    let inputHashMap = {};
    let dupplicates = [];

    for (let i=0; i < inputArray.length; i++) {
        if (typeof inputHashMap[inputArray[i]] === 'number') {
            dupplicates.push(inputArray[i]);
        } else {
            inputHashMap[inputArray[i]] = inputArray[i];
        }
    }

    return dupplicates;
}

const testData = [[4,3,2,7,8,2,3,1], [1,1,2], [1]]

// invoking solution for each test data item
testData.forEach(d => {
    console.log(findDuplicates(d));
})

Note: Concerning the discussion on tweet, updated the if condition of checking the existence of an element of the array inside the hashmap.

The function findDuplicates takes an input array as an argument and returns an array containing all the duplicate elements.

We start by initializing an empty duplicates array to store the duplicates.
We then iterate through each element in the input array using a for loop.
We see if the current element is part of inputHashMap. If it is found, then we add the current element to the duplicates array since it is a duplicate. If the element is not found in the inputHashMap, we add it to the inputHashMap since it is a new element.
At the end of the loop, we return the duplicates array.
We iterate the testData to invoke each test case against our solution.

Time Complexity

The time complexity of the above algorithm is O(n) since we iterate through the input array only once.

Ending Notes:

For those who prefer a visual guide, you can also check out the video walkthrough for this problem on YouTube using this URL: Developer Log 1 | LeetCode 442 | Find All Duplicates in an Array | Code with Asad. This video will walk you through the problem and navigate through this problem in detail. With this article and the video, you will be well-equipped to solve the problem on LeetCode using JavaScript.

In case you want to see the code used in this article or YT video, please see this GitHub URL

AWS AZ vs Region Scoped Services

Asad Ullah — Sun, 30 Apr 2023 10:19:23 +0000

A common perception in cloud development is that there isn't much to do when we work with AWS managed services. However depending on the AWS service you use, your resources are either deployed at the AZ, Region, or Global level. Each service is different, so you must understand how the scope of a service might affect your application architecture.

When you operate a Region-scoped service, you only need to select the Region you want to use. If you are not asked to specify an individual AZ to deploy the service in, this is an indicator that the service operates on a Region-scope level. For Region-scoped services, AWS automatically performs actions to increase data durability and availability. On the other hand, some services ask you to specify an AZ. With these services, you are often responsible for increasing the data durability and high availability of these resources.

A well-known best practice for cloud architecture is to use Region-scoped, managed services. These services come with availability and resiliency built in. When that is not possible, make sure your workload is replicated across multiple AZs. At a minimum, you should use two AZs. That way, if an AZ fails, your application will have infrastructure up and running in a second AZ to take over the traffic.

A key concept about whether you are using managed services or managing the infra yourself, is that AWS's customers maintain complete control of their data and are responsible for managing the security related to their content.

Do we need AWS RDS?

Asad Ullah — Wed, 09 Feb 2022 15:17:23 +0000

Like many AWS services, AWS RDS is built on top of AWS EC2. This leads to the question that why would we opt for RDS when we can run our own DB in a memory optimized EC2 instance with high performance volume attached? Using EC2 and our custom DB install will save us extra cost of RDS, right?

Yes, when our system is not sensitive to high availability.
No, when our system is sensitive to high availability and performance.

RDS provides many critical capabilities required for an highly available architecture. With RDS, we don't need to worry about:

Automated provisioning
Database engine & OS patching
Continuous backup and restore in exact point in time
Read replicas for increased read performance
Monitoring dashboards
Multi AZ setup for disaster recovery
Vertical and horizontal scalability.

Building In AWS - Things To Consider

Asad Ullah — Thu, 03 Feb 2022 10:57:36 +0000

AWS is the leading cloud provider in present times and enable us to build and deliver products faster. There are several things which AWS services provides by default i.e. elasticity, auto scaling etc. AWS provides services in almost all the areas of software development. Be it infrastructure as a service i.e. EC2, or managed services like AWS Lambda & DynamoDB etc. All of such brilliant tools make AWS a default choice for building software.

There are several points which we should consider prior to building in AWS. It can haunt our system later on if we are not very mindful of these. There are some points and hidden gotchas which are important and we can learn these from the experiences of others. We can summarize these points as following:

Availability of services (region wise)
Availability of services (distribution wise)
Cost & Pricing implications
Dealing with compliance
Limits or quotas
IAM capabilities of services

We'll look at these points one by one and try to identify the things we should be careful about.

Availability of services (region wise)

We should be mindful of presence of service in our target region before we commit the architecture. This can not be changed later on easily. Newly established region don't have all the services. It is also possible that a new service is not available in all regions.

There are scenarios when although a service is available in a region, certain features of that service is not available. Hence it is a good habit to read the documentation of a service thoroughly prior to deciding on services.

Hence the things which we should look for:

Our targeted service is available in our desired region
All the features which we intend to use are available in the desired region

Although AWS documentation mentions these things to some extent, this table from trek10 has granular details comparatively.

Availability of services (distribution wise)

In AWS, services are distributed area wise as well. Some of the services create/provision resources globally. Some of them do at regional level and some at availability zone level. We can categorize it as following:

Global services: which includes Route53, DynamoDB Global Index, IAM etc.
Regional Services: which includes S3 bucket, SNS, SQS etc.
Zonal Services: which includes EC2 instances, RDS instances, EBS volumes etc.

If a service is distributed zonal wise and our system requires regional availability, our architecture needs to take care of that replication. Similarly, if a service is distributed region wise and we need multi religion (partially global) replication, our architecture is supposed to take care of that. This is the case when the service itself doesn't provide replication. For example, RDS provides the capability of replication into different AZs.

We must consider our service of choice and the requirement in order to add components in our architecture which will take care of such replication. For example we are planning to use EC2 instances which is distributed at availability zone level. We can use auto scaling groups (ASGs) for regional availability because ASGs spreads EC2 instances in multiple AZs.

Following is an example from AWS docs for instance distribution using ASGs.

Cost & pricing (cost models)

Different AWS services have different pricing models. It will be a mistake on our part to assume that pricing model of one service will apply to another service. As we know that we pay as we use in cloud. For example:

EC2 is priced for time it runs in hours and seconds. We will be priced for a running EC2 even if it is not doing anything.
Fargate containers and Lambdas are only priced when they run and are in use.

Hence whenever we are designing a system in AWS, we must ask our client/product team:

What are the cost calculations and budget for the system to be built?
What are the traffic estimates for the system to be built?

Both of these questions will allow to make appropriate decisions regarding the services we use.

Whenever we are designing in AWS, Network Traffic is always important to be considered. The golden rule is:

Don't forget the traffic and cost drivers

For example, we are priced whenever traffic is moved from region to another region or from one availability zone to another availability zone in EC2. Another example of cost model is the use of NAT gateway. Not only we pay for NAT gateway, but we also pay for internet gateway.

Hence we should always try to identify the cost drivers in our architecture. In some architectures, heavy data load is the cost driver. For example in a webhook architecture, we should be mindful of following:

Event size
Number of events

Cost driver here will be outbound traffic. As the number of webhook endpoints of clients increases, we have to dispatch more events from our system to internet. Hence the outbound traffic.

Dealing with compliance

Whenever we are designing a system, we should also be careful about the compliance which is required. Sometimes the client companies require certain compliance and sometimes governments require some standards to be followed. For example, PCI-DSS, HIPPA/HITECH etc.

We see in AWS description and documentation that it is compliant to certain standards. But in reality, this is an half answer. Instead of the whole AWS cloud,

Certain aws services, regions and edge locations are compliant to a standard or framework.

Hence, when we are making a choice of region or service, we need to check if that region or service is compliant to our target framework or standard.

For example, elasticache or memcached are not scoped in china region. Some edge locations are not scoped or covered in compliance. Hence if we are using AWS cloudfront, we are not sure which edge locations will be used and whether those edge locations are scoped in compliance framework or not.

These are the points related to compliance which we must consider before finalizing the architecture, or presenting the audit report to audit authority.

Limits or quotas

A limit is the constraint which protects us from excessive use of a services - protecting us against huge bills. Most of the quotas can be increased by requesting to AWS support. There are some limits which can't be increased. Common upper limits can easily be found in AWS documentation. If some limits are not clear, we can reach out to AWS support team.

All the AWS services are limited in some ways. For example,

We can't spin 100 EC2 instances at once.
By default port 25 of SMTP is blocked for EC2. It is not visible in security group either. However, we can request AWS to remove this filter.
SNS has different throughput limits per different region. It will be higher in us-east-1 as compared to Frankfurt region. Hence some services behave differently depending on the region.

Some of the limits are documented in a very subtle way. It is very easy to overlook them. Hence we must do following:

Read the docs carefully regarding limits
Read the service FAQs carefully and identify if there are any limits.

IAM capabilities of services

All AWS services use IAM to control access to services using policies. It is very often that we rely on IAM to achieve certain architectural goals. For example tenant isolation using separate VPC per client.

We must consider that:

Some services can have different IAM featres. For example IAM features are only at resource level like start or stoping EC2 containers.
Some AWS services allow access on the basis of tags and policies. For example all the resources having a particular tag.
Some other services don't allow conditions based access or policies. Or don't allow resource level access.

Hence we shouldn't take resource based access or policy based access for granted and shouldn't assume that it will be available for all services in a similar way. We should always consider whether the access capability we desire is available in our target service. AWS IAM documentation is great for this purpose.

Summary

Since we have already discussed all the gotchas in detail, hence whenever developing an architecture in AWS,

Gather knowledge of services at broad level to get an idea of what is possible.
Once the services are selected, go into deeper details of the services to find constraints and limitations
Go through the checklist which is also discussed in this article to avoid common pitfalls.

Note: I took help from my experience and existing resources for this article. Any mistake or factual inaccuracy can be reported in comments. I will try my best to maintain & update this with time to time.

Reoucrces:

How to do serverless in AWS?

Asad Ullah — Mon, 10 Jan 2022 09:12:44 +0000

AWS serverless ecosystem consists of a lot of tools and services. Although there are couple of guides on the implementation details of individual services, there is not enough material highlighting the principles involved in choosing an AWS service. A wrong choice can be a costly mistake when our serverless system hits scale. This article is more of a survey of serverless fundamentals in AWS. It will briefly touch upon composition paradigms and the services which can be used for any of these paradigms. Common use cases of AWS services and their comparison will also be discussed.

Before we proceed to architect a serverless system, we must understand what serverless systems offer and what are the common use cases for serverless systems.

Why serverless?

Serverless is no silver bullet and it promises certain things which makes it useful for certain scenarios.

It allows us to prototype things faster and thus enables us to move from ideas to market.
It makes us focus more on our product instead of spending time on infrastructure management.
It is a low cost solution because it follows the Pay as you use model.
Scalability and high availability are built into the AWS services.

Considering the promises serverless do, there are some use cases for which serverless makes more sense.

Popular Use Cases

Serverless architecture is best used to perform short-lived tasks and manage workloads that experience infrequent or unpredictable traffic. Some of the use cases are:

Trigger Based Tasks: Any user activity that triggers an event or a series of events is a good candidate for serverless architecture.
Building Restful APIs: You can leverage Amazon API Gateway with serverless functions to build REST APIs that scale with demand.
Asynchronous Processing: Serverless functions can handle behind-the-scenes application tasks, such as rendering product information or transcoding videos after upload, without interrupting the flow of the application or adding user-facing latency.
Web Applications: Evolving nature of SaaS products and web applications make them suitable candidate for serverless.

How to design serverless architecture?

Now we understand the benefits and popular use cases for serverless, we will jump to the fundamentals of serverless systems.

Whenever we are designing serverless or microservices, we must define the events in our system, bounded context of our APIs and the composition paradigm we will be choosing for our system.

Events & Bounded Context

It is better to divide large business operations to small bounded contexts. This enables us to clearly define the responsibility of any given part of our system. We can define this process to three steps:

Be explicit about the inter-relationship of our bounded contexts (small broken pieces of our large business operation).
Define events and service boundaries for these bounded contexts.
Group events by reducing data dependencies.

This infoq article has a good guide on bounded contexts.

A bounded context can be any part of our system clearly depicting the flow. One example of a bounded context in a serverless system can be seen in the following diagram.

We'll discuss the design decisions about these services later in the article.

Composition

There are two paradigms to compose serverless systems:

Orchestration
Choreography

Each of these paradigms have different characteristics which enable us to make the choice for our use case.

Orchestration

Synchronous - Request Response paradigm
Services are controlled by a centralized function or process.
The controller function needs to wait for each downstream process to complete and return a response.
Services are very tightly coupled
Failure could stop the entire process / flow

Choreography

An asynchronous or event driven paradigm
Services work independently and are decoupled from each other
Failures and retries are easier to manage
Difficult to implement timeouts.
End-to-end monitoring and reporting are comparatively difficult.

Since we understand bounded contexts and composition paradigms, we will move on to implementation of these principles in AWS.

Serverless tools in AWS

There are several serverless services in AWS. Some of them are listed down below in their respective category.

Compute
- AWS Lambda
- AWS Fargate
Application Integration
- AWS Event Bridge
- AWS SQS
- AWS SNS
- AWS Step Functions
- AWS API Gateway
- AWS AppSync
Data Store
- AWS S3
- AWS DynamoDB
- AWS RDS Proxy
- AWS Aurora Serverless AWS Kinesis, AWS Cognito and AWS CloudWatch are also used often in serverless systems.

Serverless Orchestration in AWS

AWS step functions are used for serverless orchestration in AWS. Step functions are all about modelling business transactions through series of state transitions. Step functions enable us to do end to end monitoring and reporting via audit histories. The order flow is modeled and source controlled.

Above is one of the example of a step function flow. We can clearly see it as state machine. There are two types of step functions workflows:

Standard (Workflow which takes more than 5 minutes to complete)
Express (Workflow taking less than 5 minutes and when we need high execution volume)

Some of the common use cases for AWS step functions are given below

Microservices orchestration
IT Automation
Data processing and ETL orchestration

Implementation details and extended flow examples can be studied at AWS official examples page.

Serverless Choreography in AWS

Choreography in AWS allows us to modify each step of the flow independently. It also enables us to scale the different parts of our system independently of each other. Since we have already discussed bounded contexts and events, events allows us to extend functionality in choreography comparatively easily.

There are two considerations which we must discuss before proceeding:

End to end monitoring and reporting is comparatively difficult.
Difficult to implement timeout logic.

Let's discuss the example choreography architecture given below:

There is no centralized service controlling everything. Instead each part of the system relies on the incoming event, does its part and forwards it to a destination. The whole system is driven by events. For this example:

A client makes request to API which is powered by AWS API Gateway
API Gateway integrates with AWS Lambda Function in an asynchronous way (more on this later.)
AWS Lambda does its processing and pushes the event to AWS EventBridge's event bus.
EventBridge have rules and it notifies the matching rule destinations.
A Lambda and an SNS topic can also be destination for an event from event bus.

As we saw that the question of choosing SNS & EventBridge at their respective places is still not answered. At this stage, there should be more questions like:

When to use AWS SQS and when to use AWS SNS?
When to use an AWS SNS and when to use AWS EventBridge?
What is synchronous and asynchronous invocation of a Lambda?

By a quick read about these services, we find out that some services appears to do very similar things like SQS, SNS and EventBridge. In order to have the correct mental model for these services, we must understand how these services integrate with the compute part of our serverless system i.e. Lambda.

Lambda Integration Models

There are three ways in which Lambda integrates with the other AWS services.

Poll based integration (Synchronous)
Push based integration (Synchronous)
Event based integration (Asynchronous)

Before we proceed, lets discuss the synchronous and asynchronous invocation of lambda functions.

Synchronous Invocations

In synchronous invocation, we wait for the function to process the event and return a response.

Lambda runs the function and waits for a response
Lambda returns the response from the function's code with additional data, such as the version of the function that was invoked

Asynchronous Invocations

In asynchronous invocation, Lambda queues the event for processing and returns a response immediately.

Lambda places the event in a queue and returns a success response without additional information
A separate process reads events from the queue and sends them to your function

AWS has very detailed documentation for both kind of invocations. Let's move on to the lambda integration models.

Poll Based Integration

Lambda is a service which contains many resources such as our lambda function, event queue, event resource mapping etc. In this kind of integration, event resource mapping is responsible for polling the target service and fetching data when available.

Lambda polls the records from stream or queue using event resource mapping
Resource mapping then invokes your function synchronously based on BatchSize or BatchWindow
Each event that your function processes can contain hundreds or thousands of items

Below are the services which do poll based integration with AWS Lambda:

AWS DynamoDB Streams
AWS Kinesis Streams
AWS SQS
AWS MQ
Apache Kafka (managed and self-managed both)

Below is an example of this kind of integration from AWS Docs.

Push Based Integration

In this kind of integration, services themselves are responsible for pushing the event to Lambda Service.

The services pushes an event to Lambda
Lambda then invokes your function and return a response

AWS API Gateway, AWS Cognito & AWS CloudFront do this kind of integration with AWS Lambda. The example diagram in choreography section can be seen as an example of API Gateway's integration with Lambda.

For the API Gateway scenario, there is a catch here. Since our Lambda function is invoked synchronously by lambda service, it returns a response. There is a way to configure Lambda so that it integrates with API Gateway in an asynchronous way. Official docs has a very good guide for it.

Event Based Integration

In this kind of invocation, services invokes the lambda and immediately gets success response after handing over the event. Lambda then processes the event in the background.

Services hand off the event to Lambda and Lambda handles the rest
Lambda manages the function's asynchronous event queue
We can configure Lambda to send an invocation record to another service
- SQS Queue
- SNS Topic
- Lambda Function
- EventBridge event bus

S3, SNS, EventBridge & CloudWatch do this kind of integration with lambda. Below is an example where SNS integrates with Lambda in an asynchronous way.

Most of the times, we are dealing with poll based integration and event based integration. Below is a short visual summary of all three types of integrations.

Now we understand different composition paradigms, how they are implemented in AWS and how Lambda integrates with the serverless services in AWS. Let's discuss briefly the design principle and use cases for some common services.

When to use AWS SQS and AWS SNS?

SQS and SNS are used to decouple our applications in cloud. But both of these services have some very distinct characteristics making them suitable for different purposes.

SQS

SQS is basically for 1:1 reliable asynchronous communication between two entities.
SQS temporarily holds messages and is owned by the consumer. Its job of consumer to get the message from SQS. (REMEMBER: Lambda polling) Lambda does this for us automatically.
It is used to decouple our services in a way where we want to process the messages as per the capacity of consumer.

SNS

SNS is for 1:N message/event publishing (pub/sub model). It is also called “Fanning out the events”
It is used for application where we need high throughput. Which means we want to fan out events as soon as they arrive. It is the job of SNS to publish the event to subscribers.

When to use SNS & EventBridge?

SNS & EventBridge are both used to distribute events. EventBridge is under the hood same as AWS CloudWatch Events API but it provides more features like integrating with external services. SNS is more useable for fanning out events to different services while EventBridge's intended use is for Application Integration.

SNS

SNS is for 1:N message/event publishing (pub/sub model). It is also called “Fanning out the events”
It is used for application where we need high throughput. Which means we want to fan out events as soon as they arrive. It is the job of SNS to publish the event to subscribers.

EventBridge

EventBridge is for 1:N ((N:N sometimes) for message distribution
Recommended to be used for application integration like SaaS or third party integration like datadog, shopify etc.

Sometimes people face difficulty in the limit of 5 target on a matching rule when they try to use EventBridge in place of SNS. What we can do is that to have an SNS topic as a destination of matching rule and route the event to SNS for fanning out. AWS EventBridge is primarily meant for routing event in our system. The convention is to have a separate rule against each service to which we want to route an event. This is good for separation of concerns.

Conclusion

We discussed bounded contexts and composition paradigms, how to implement them in AWS and mental models for some of the services central to event driven systems. After having the knowledge of all these things, we should be able to make an educated choice for our system on the basis of our budget, our use case, our team size and the project timelines. There is no right or wrong for most of the people and systems. But these design decisions and principles become important when we are dealing with serverless at scale.

This whole article is meant to serve as a mental model for designing serverless in AWS. For the implementation details of individual services, AWS Docs are the best place to go.