# Questions tagged [complexity]

Complexity is the analysis of how the time and space requirements of an algorithm vary according to the size of the input. Use this tag for reviews where the "Big O" is a concern.

405 questions
Filter by
Sorted by
Tagged with
1 vote
202 views

### Printing subarrays ⚡

I was trying to to print all subarrays of an array in quadratic time. Here is my code: ...
35 views

### Calculate maximum value of expression for potential associations

I have an algorithm that calculates the maximum value of an expression that is made from numbers and * or + by adding parentheses. It has 3 nested loops, so the time complexity should be N^3 ...
70 views

### Algorithm for twoSum

This is my PHP algorithm for the twoSum problem in leetCode: ...
49 views

### Time complexity of several methods of reversing a domain name string

Note: I'm aware of this existing post which is similar. However, it does not address all my questions sufficiently. I have the following three functions, all of which do the same thing: reverse a ...
113 views

### Finding the minimum element of a stack of numbers

As part of an online programming challenge, I wrote a program that implements a stack of integers, supporting adding and removing elements, finding the last inserted element, and the minimum element. ...
• 131
60 views

### Hackerrank's New Year Chaos problem (find minimum number of swaps to reach a permutation)

I am trying to solve the problem to Hacker Rank's New Year chaos problem. I have come up with a not so elegant solution. This is failing to adhere to the timing constraints of Hackerrank My approach ...
1 vote
134 views

### group countries by language in JavaScript

I need a better implementation than the below code (O(N) Solution), I am grouping countries by language ( data ) is the countries JSON, each country could have 0, 1 .. or more language as the object ...
267 views

### Separating odd numbers and even numbers into two vectors in C++

I'm learning C++, and would like some guidance. I'm pretty sure I'm doing something wrong. This algorithm runs in O(n) time and uses O(n) external space. Could I make a more efficient algorithm for ...
• 13
142 views

### Brute force to solve refund amount in a payment/invoice domain

I work at a major Swedish insurance company. I'm in charge of a service that matches bank payments with invoices. I will not show the details of that match logic. But one outcome of the match is that ...
• 670
100 views

...
• 123
141 views

### Find the highest product of three numbers in a list (Python)

I wrote the below as a solution to: Problem Find the highest product of three numbers in a list Constraints Is the input a list of integers? Yes Can we get negative inputs? Yes Can there be ...
• 187
1 vote
198 views

### SumList Cracking the coding Interview

Sum of 2 numbers, represented with linked lists, where digits are in backward order or forward order. Backward order Example INPUT:(7->1->6) + (5->9->2) = 617+295 OUTPUT: 2->1->9 = ...
79 views

### Optimizing methods with multiple if checks on getter values

I have a method where I fetch user input, check if certain values exist, and based on that build my own custom input object that I would use to search in a database. The code for the search method is ...
• 121
108 views

### Find the largest decrease in a sequence of numbers

I have written a function that takes as input a list of 5 numbers, then the program's goal is to return the largest drop in the list. It is important to understand that [5, 3, ...] is a decrease of 2 ...
110 views

### Finding unique top sums from multiple lists

My question arises from this post on MSE where I have provided an answer to solve the question : There are multiple lists given. The number of lists is arbitrary. Each list contains numbers and is ...
• 101
1 vote
440 views

### URLify a given String - replace spaces with %20

I have written a code to replace all spaces in a String with %20. ...
• 113
259 views

### Can I further optimize this solution for HackerRank's “Making Candies”?

My C++ solution for HackerRank's "Making Candies" problem, reproduced below, is as optimized as I can make it and appears similar to what others say are optimal solutions. However, six of ...
• 258
102 views

### Substring search in Java

I am trying to make an algorithm that will find the index of a given substring (which I have labeled pattern) in a given String (...
• 361
80 views

### Speed-up anomaly detection for pandas dataframes with vectorized operations

Motivation: I very often face a task where I need to check that dataframe's values are correct or not. Based on it I can create another dataframe with True/False values which are based on the first ...
• 101
70 views

### Optimize nested loops for counting the total number of selections

The question is: To select 2 numbers out of n positive integer inputs (order matters), where the number that is placed anywhere before the second must be greater than the second by a given number m. ...
1 vote
82 views

### Monotonic stack - complexity analysis

I tried following the official solution of LC975 (https://leetcode.com/problems/odd-even-jump/), using a monotonic stack - i.e., I reimplemented their solution (Approach 1) from python in C++. TLDR ...
• 196
116 views

### Is this an efficient/correct way to get largest Prime factor?

Is this an efficient way to get the largest prime factor of a given number? Other solutions I found involved nested algorithms. ...
• 133
239 views

### strstr implementation with python and sets

Please review my strstr implementation in terms of time/space efficiency and overall readability. I am preparing for a coding assessment coming up as I am looking to pivot my career from Physics to ...
• 31
1 vote
62 views

### Sorting Algorithm using Modified Merge sort

I've been messing around with merge sort. Instead of doing a recursive division of the array I chose to keep keep track of the middle index of every three numbers. Using the index of the middle number,...
• 43
3k views

### Merge arrays in objects in array based on property

I have the following code which takes an array that might have duplicate ids and will merge the items of those duplicate, and ...
• 189
254 views

### Performant Sort function for big arrays

In sort(arr), I want to sort an array. Children must be beneath their parent. And children of the same parent are sorted using ...
• 143
553 views

### LeetCode 3Sum Java Solution

I have this Java solution to LeetCode's 3Sum problem. I would be really grateful if I could get feedback on correctness, scalability, efficiency, coding best practices, and OOP design. I'm relatively ...
145 views

### 2D Array Word Search: Complexity and Optimization

🧩 Objective Determine whether a given word is contained in a 2D Array word search. 🔎 Question 1. What are the time and space complexities of the current algorithm? Time complexity Linear: \\$O(2(r * ...
• 239
198 views

### Generate unique string permutations recursively

🧩 Objective Write a recursive method for generating all permutations of an input string. Return them as a set. See: Recursive String Permutations - Interview Cake 🔎 Questions 1: How does the ...
• 239
1 vote
409 views

### Most efficient solution for USACO: Cow Gymnastics - Python

I was trying to figure out this problem, and I did. However, my code is so abhorrently ugly that I want to tear out my eyeballs when I look at it: ...
109 views

### Cyclomatic Complexity (complexity)

I have a program for finding shortest distance/path and I got a correct answer but I am getting an issue i.e., "Function 'shortestPath' has a complexity of 9. Maximum allowed is 6." This is ...
140 views

### Ensuring if an object is Assignable from a class type

I am trying to ensure type in the below method. How to reduce its cognitive complexity to below 15 from the current 27? It looks more readable as it is? Is there a way to break this down to make it ...
• 33
262 views

### 01 Matrix is too slow when solved using DFS

I tried solving Leetcode 01 Matrix problem. It is running too slow when solved using DFS approach. Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell. The distance ...
• 129
648 views

### Most Efficient Solution for USACO: Triangles - Python

I'm trying to solve this problem with Python 3.8. In my code, I used 3 nested for loops to check every single point and storing the largest area with each set of points. This program works fine, but ...
486 views

### Best Algorithm for solving USACO: Photoshoot - Python

I was trying to solve this problem with Python 3.8. I couldn't find a way other than to brute-force calculate all the possible permutations then check which permutation was valid. The program works ...
58 views

### What is the time complexity problem I need to manage on a Hackerank "Ransom Note" - my code runs perfectly [closed]

I am trying to solve the "Ransom Note" problem on hackerank. Why isn't my code getting submitted? What can I do differently? is my total time complexity, in this case, it is O(n^2)? ...
• 159
2k views

### Dynamic Array Based Stack in C

I wrote a dynamic stack in C that uses an array as a structure. I tried to maintain O(1) for push and pop and believe I have done so. I want to know what can be written in a cleaner way and if there ...
• 123
46 views

### Count number of square integers in a given range of ints (faster function?)

The function below passes most test cases: ...
• 213
242 views

### Car Pooling algorithm time complexity

I created a solution for the car pooling algorithm. Problem: You are driving a vehicle that has capacity empty seats initially available for passengers. The vehicle only drives east (ie. it cannot ...
138 views

### Determine the complexity of sorting a binary array

The challenge is to sort an integer array containing only ones and zeros with the lowest complexity possible. As always, I am interested in any improvements suggested but in this question I am most ...
• 279
83 views

### Closest Pair heuristics, graph with adjacency matrix in C++17

I was trying to solve a problem that was briefly mentioned at the beginning of the "The Algorithm Design Manual" by Steven Skiena (Ch 1, Problem 26). It took me some time to build a working ...
5k views

### The fastest way to find one unique value when all other values are the same

I have completed this question and I am wondering what is the fastest way to solve it. The question is "There is an array with some numbers. All numbers are equal except for one. Try to find it!&...
• 333
59 views

### Benchmarking multiple implementations of a Code Kata: queue for the self-checkout tills at the supermarket

I was reading this question: Why is my function timing out when run with a larger data set? And although I couldn't quite grasp the OP's implementation and so didn't feel like answering. I did some ...
• 3,955
1 vote
95 views

### Parser for file made up of sections

I'm parsing a file made up of various sections. I have a current_section variable that tracks which portion of the file I'm currently processing and the following <...
1k views

### Computing the item price and vat for a given pricing, order, and exchange rate

How can I improve the readability of the below function using a list comprehension? Also, is there a way to improve items() performance? ...
42 views

### Improving time complexity for Count the Islands DFS

For game AI development, I am currently using a slight modification on the DFS "count the islands" problem (specification below) as a solution to the ...
• 153
1 vote
45 views

This code unzips the downloaded subtitle files and maps them to their corresponding video file. Currently, after pairing video files with their corresponding subtitle files, it links them by renaming ...
1 vote
161 views

### Faster binary search to find the index in Python?

I am implementing a binary search algorithm and my code is as shown bellow: ...
• 325
1k views

### Time and Space Complexity of Prime factorization

I have written a function that prints all the prime factors for a given number. Here is my code ...
• 590