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.

Filter by
Sorted by
Tagged with
2
votes
2answers
94 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 ...
2
votes
0answers
35 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 * ...
0
votes
1answer
69 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 ...
1
vote
1answer
64 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: ...
2
votes
2answers
69 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 ...
2
votes
1answer
56 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 ...
6
votes
1answer
93 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 ...
3
votes
2answers
208 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 ...
7
votes
2answers
112 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 ...
-4
votes
1answer
49 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)? ...
2
votes
2answers
66 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 ...
3
votes
1answer
34 views

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

The function below passes most test cases: ...
2
votes
1answer
95 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 ...
7
votes
2answers
123 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 ...
5
votes
1answer
61 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 ...
23
votes
9answers
4k 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!&...
2
votes
0answers
30 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 ...
1
vote
1answer
59 views

How can I reduce the complexity of this ruby method?

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 <...
6
votes
4answers
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? ...
2
votes
1answer
31 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 ...
1
vote
1answer
44 views

Link downloaded subtitle files and video files

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
1answer
46 views

Faster binary search to find the index in Python?

I am implementing a binary search algorithm and my code is as shown bellow: ...
4
votes
2answers
526 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 ...
5
votes
4answers
249 views

LeetCode: Roman to Integer in Java

I tried solve this easy leetcode challenge in java. Challenge link Here is my solution ...
8
votes
3answers
2k views

Counting Balanced numbers in a given array

I am trying a code challenge. Here is the problem description: When an element is deleted from an array, the higher-indexed elements shift down one index to fill the gap. A "balancing element&...
2
votes
1answer
32 views

Time and Space Complexity of Leetcode Problem #31. Next Permutation

The question is as follows: Given a collection of distinct integers, return all possible permutations. Example: ...
1
vote
3answers
122 views

Refactor Java code

I was trying to solve the following question: You are given 2 arrays: one representing the time people arrive at a door and other representing the direction they want to go(in or out) You have to ...
2
votes
1answer
32 views

What is the optimal way to retrieve a list of sorted dates in a list of sorted periods in python?

Suppose I have a list with N sorted dates and M non-overlapping sorted periods with start date, end date (inclusive), and a tax rate for example. I have to make an efficient algorithm retrieve all tax ...
1
vote
0answers
33 views

Why is my function timing out when run with a larger data set?

I am working on a Code Kata ...
2
votes
1answer
68 views

Finding the closest pair of numbers which add to a target number

This function takes two lists of same length and a target number: the number which is to be summed. The function then returns a list of pairs whose sum is closest to the target number than any other ...
0
votes
2answers
73 views

Python: Find pairs of numeric palindromes that sum up to another palindrome

I am trying to identify and print pairs of 4 digit palindromes that sum up to a 5 digit palindrome. This is what I have so far ...
11
votes
5answers
2k views

Are the sum of two numbers desired?

Given two input arrays [-1, 8, 3] and [3, 7, 2] your function will return true if any two of the numbers in the first array add ...
3
votes
1answer
91 views

Finding Common Items in arrays

My goal is to get a list of related statementIds in order of most repeated. In my database I have stems(Words): ...
3
votes
1answer
91 views

The optimized way to find the top k leading candidates from a unsorted hash map in python

I need to write a method that will accept a timestamp and takes an array of votes, I need to return the k leading candidates with that timestamp. I came up with the ...
1
vote
3answers
121 views

Transpose 2D Matrix in Java - Time & Space Complexity?

Here's my algorithm / approach for transposing a 2D Matrix on the main diagonal. Before: a L M d b G c N H K e F I J O P After: ...
0
votes
2answers
149 views

Java Palindrome - Time & Space Complexity

Which of these three methods is the most efficient? Also, what is the time & space complexity of each? ...
4
votes
3answers
779 views

How to do these extraction/computations efficiently?

I have a set of products(e.g. P0006, P0009, etc.) and a set of production lines (eg. L1H175, L2H175). A product can be produced on a subset of the lines set (and not necessarily all of them). If we ...
1
vote
0answers
59 views

My C# code to evaluate order of algorithm is returning logN or N^3 instead of N for simple loop [closed]

As a learning exercise, I am writing a library to evaluate the complexity of an algorithm. I do this by seeing how long the alorgorithm takes for given inputs N, and then do a polynomial regression ...
2
votes
1answer
56 views

Find the maximum GCD of a number with respect to all the values in an array for competitive programming

Here is the Question. Find the largest GCD of the input variable with the values of an array. Inputs are as follows:- First-line contains two integers, N and Q. Second-line contains N integers which ...
3
votes
1answer
91 views

Searching an element in a 2D sorted array

I had to write a code (as an exercise) that receives a 2D row wise and col wise sorted array and an element, and return true is the element exists in the array. The first thing that came to mind when ...
1
vote
0answers
21 views

Intersection of Two Arrays - Space Time And Complexity [closed]

The problem is as follows: Given two arrays, write a function to compute their intersection. The below code is my solution.I'm just curious as to what the space time and complexity of below algorithm ...
2
votes
1answer
80 views

Permutation 1…N. Answer queries “How many numbers between [X,Y] position are in the interval [L,K]”?

So I am solving this task: We have an permutation of the numbers 1..n. I need to answer m queries: -How many numbers between X-th and Y-th position are in the interval [L,K] (<=k and >= L)? So my ...
3
votes
1answer
95 views

Using Python to search a sorted 2D Matrix

Code Problem ...
0
votes
1answer
64 views

Choosing between 2 Fibonacci alternatives [closed]

Task: Return the fibonacci value at a given index. e.g: input: 6, return: 8. Algorithm 1: ...
3
votes
1answer
196 views

Algorithm to find the Array Balance Point

Task: Find the balance point of an array; return the index that if you break the array into left and right at that point will ...
1
vote
0answers
93 views

Binary Heap module in Typescript/Javascript supporting min-heap and max-heap

About binary heaps: https://en.wikipedia.org/wiki/Binary_heap The purpose of this module is to allow quick and efficient priority queue management, compared to linked list. Efficiency: insert: \$O(\...
2
votes
0answers
31 views

Snake string implementations

This snippet uses a string as an output. As we iterate through the input string, I just keep appending a character to the string and I know this just pretty much creates a new string everything I add ...
1
vote
0answers
66 views

leetcode 230: kth smallest element in a Binary Search Tree

Here is my implementation: the goal of the algorithm is to find the kth smallest element in a BST. ...
3
votes
0answers
134 views

Calculating the total sum of inversion count for all subarrays

My approach was to visit all inversion count pair and count how many subarrays these pair contribute. Visiting every pair requires \$\mathcal{O}(n^2)\$ time, but I want an optimized version of this, ...
2
votes
1answer
296 views

CCC '19 S5:Triangle: The Data Structure

This problem is from [CCC2019]: https://dmoj.ca/problem/ccc19s5/ (Canadian Computing Contest 2019) and I have implemented it in C++. I used sequence [A054237]: https://oeis.org/A054237/table to ...

1
2 3 4 5
8