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
0
votes
0answers
15 views

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

I am working on a Code Kata ...
2
votes
1answer
61 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
70 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
82 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
86 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
64 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
80 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
774 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
56 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
52 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
89 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
20 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 ...
2
votes
1answer
64 views

Using Python to search a sorted 2D Matrix

Code Problem ...
0
votes
0answers
17 views

Simplifying code for deleting directories

Background info: An FSObject is a dir or a file. The structure definition for a directory (dir) is the following (define-struct dir (name owner contents)). A ...
0
votes
1answer
58 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
81 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
55 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
30 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
51 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
116 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
236 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 ...
2
votes
1answer
32 views

Finding minimum weighted matching in sink source graph

I have three lists of nodes. sources sinks pipes There is a directed weighted graph from sources to pipes to sinks. Sources are only connected to pipes and pipes only to sinks. But sources are not ...
4
votes
1answer
208 views

Hacker Rank Climbing The Leaderboard

This has been asked a couple of times but here is my implementation in C++. I have 11/12 solutions completed. The 6th test case which has 200000 intial scores and Alice has even more scores causes my ...
4
votes
1answer
68 views

Finding all simple (without internal cycles) paths in a directed graph with total >1.0 weight

Assume directed graph with each edge being weighted by some positive float. Problem: find all simple paths (in other words, ...
8
votes
3answers
766 views

Find the smallest positive integer that is absent from a given array

I made the acquaintance of big-O a couple of weeks ago and am trying to get to grips with it, but although there's a lot of material out there about calculating time complexity, I can't seem to find ...
2
votes
1answer
51 views

Circular Doubly Linked List with generators

I didn't find an implementation on CR of the circular doubly linked list, using generators. Hence, I tried it myself. Description The class Deck represents a ...
2
votes
2answers
83 views

Print Integers in a Pyramid

I need to write a method that will print the integers from [1, maxValue] in a pyramid where the nth row contains ...
5
votes
2answers
125 views
2
votes
1answer
53 views

In-Place Merging of Two Bubble Sorted Linked Lists (Python)

I'm following a tutorial on merging two bubble-sorted Single Linked Lists in Python. merge1 does the merging by creating a new list with maybe \$O(N+M)\$ memory ...
2
votes
1answer
51 views

Merging Two Bubble Sorted Linked Lists (Python)

I'm following a tutorial on merging two bubble-sorted Single Linked Lists in Python. merge1 creates a new list and does the merging. Other than naming ...
0
votes
1answer
100 views

Create custom Queue class with O(1) Enqueue and O(1) Dequeue [closed]

I am implementing a Queue class in C# using a Node/LinkedList class that I also implemented, and I wonder if there is a way to implement the enqueue and the dequeue methods, both in algorithmic ...
3
votes
2answers
70 views

Time and space complexity of base conversion code

I have an algorithm that performs the base conversion. The input is a string and two ints b1 and b2. The string represents an int in base b1 and converts it into base in b2. My code is: ...
4
votes
1answer
121 views

Min Heap Priority Queue

This was a part of one an assignment I found online and tried to solve it myself. The objective was to implement a Priority Queue using Min Heap and use Array as the underlying data structure to ...
4
votes
3answers
119 views

Find the first missing positive integer in an array of integers

The problem is the one explained in Given an unsorted integer array, find the first missing positive integer Given an unsorted integer array, find the first missing positive integer. For ...
3
votes
1answer
226 views

LinkedList Swift Implementation

Linked List Implementation in Swift Swift 5.0, Xcode 10.3 I have written an implementation for a doubly linked list in Swift. As well, I decided to make the node class private and thus hidden to the ...
5
votes
2answers
206 views

LeetCode: Linked List Cycle

Challenge https://leetcode.com/explore/interview/card/top-interview-questions-easy/93/linked-list/773/ Given a linked list, determine if it has a cycle in it. To represent a cycle in the ...
8
votes
1answer
165 views

An array with \$O(\log\ n)\$ time complexity for all operations

Does this exist already? It's an array (=variable-size list with integer indices) where add/remove/set and get all take \$O(\log\ n)\$ time. I couldn't find this anywhere, so I made up the name "Log-...
1
vote
1answer
640 views

Python Implementation: Summer of 69

SUMMER OF '69: Return the sum of the numbers in the array, except ignore sections of numbers starting with a 6 and extending to the next 9 (every 6 will be followed by at least one 9). Return 0 ...
-2
votes
1answer
60 views

Challenge - Construct binary tree from array [closed]

A coding challenge to construct a binary tree from an array. ...
3
votes
2answers
377 views

Finding unpaired number in an odd length Array of integers

codility OddOccurrencesInArray: A non-empty array A consisting of N integers is given. The array contains an odd number of elements, and each element of the array can be paired with another element ...
2
votes
3answers
133 views

Modeling, view and projection transformation using vector and point in homogenous form

I know this is horrible code. This program is for performing modeling, view and projection transformation. The program reads input from scene.txt and outputs the <...
2
votes
1answer
61 views

Find the number of all specific substrings in a string

I would like to ask a code review regarding a concrete exercise. Let's suppose I have to get the number of all specific substrings in a string. We call something specific if any of these conditions ...
2
votes
1answer
95 views

Kruskal MST algorithm

I came up with the following code by following Prof. Sedgewick's lecture on Coursera. Please review this code and let me know if there is anything that I got wrong in implementing Kruskal's ...
1
vote
1answer
278 views

Rotate matrix clockWise and counter clockWise

This code is a mix of the same question one time rotating to the right and one time to the left. I tried to simplify the code since I'm struggling with all of the indexing here. https://leetcode.com/...
2
votes
1answer
84 views

Coding Challenge: Return The Smaller String

A coding challenge in which we are to write a function that compares two strings and returns the one that is smaller. The comparison is both lexicographical and numerical, depending on the content of ...
3
votes
1answer
103 views

LeetCode: Best Time to Buy and Sell Stock II

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/ Please review for performance. Say you have an array for which the i-th element is the price of a given stock on day i. ...
2
votes
0answers
150 views

Frog Jump time complexity

I have tried to work out the Frog Jump task on Codility. The algorithm for solving this is rather simple but the maximum score I am able to achieve is 55% (also 44% with modulus operations). A ...
8
votes
1answer
852 views

Regular Expression Evaluator

Task to be accomplished: Write a function that takes two strings s and p as arguments and returns a boolean denoting whether s matches p. p is a sequence of any number of the following: a-z - ...

1
2 3 4 5
8